Tree Packing
Tree packing stores a prefix that several rows share once. Rows that start identically — the same instructions and document, then a different question and answer — become branches of one tree inside a packed row. A branch attends the shared prefix and itself, never a sibling, so every example gets the logits, language-model loss and gradients it gets when packed flat, at fewer tokens.

SFT only (scripts/training/sft.py), raw (not pre-processed) text datasets: GPT-OSS, Qwen3 and
Qwen3.5/3.6 (dense and MoE) on flash_attention_4 or flash_attention_2, and GLM-5 Next on its SDPA
backend.
YAML
packing: true
tree_packing: true
tree_share_markers:
- "\nQuestions:\n"
tree_share_requires: "\nDocument:\n"tree_share_markers is required: rows whose message before the final turn is identical up to and including
one of its strings are examined together. tree_share_requires shares a row only if its text occurs before
the marker, which leaves rows that put the long part after the marker alone instead of sharing a short
header. Types and defaults of every tree_* option: SFTScriptArguments.
What is shared
The markers only decide which rows are examined together. Each split is ordered by a digest of the text up to the marker, so rows over one document become adjacent. Every row is then rendered and tokenized whole, exactly as the flat path does it, and a run of adjacent rows shares what its token sequences have in common. A row whose tokenization differs one token into the "shared" text shares one token less; nothing is assumed from the text.
- Sharing stops one token before a row's first trained token, so the token a completion is predicted from sits in the branch with it. Two rows with one prompt and different answers share all but the last prompt token.
- Rows may share at several depths: the document, then the start of what follows it.
- A group longer than
max_lengthsplits into several trees that each repeat the prefix. A row longer thanmax_lengthon its own is dropped, as on the flat path. - A row with no marker, or with the marker more than once, shares only with an exact duplicate.
- A shared span under 16 tokens is repeated per row, not split off.
The digest order replaces the dataset's row order, in both splits. The trainer still shuffles packed rows every epoch.
Measured on Halo 1.2.0. The gain is the share of tokens that sit in shared prefixes: a synthetic corpus where half the
rows share a document of about 6k tokens packed into about 1.7× fewer rows at 64k tokens per row (116 to 69 on
gpt-oss-20b, 130 to 77 on Qwen3.5-35B-A3B). A tree step costs what a flat step costs where sliding-window layers
dominate (gpt-oss-20b at EP8 on FA4, 4.45 s against 4.48 s). Qwen3.5-35B-A3B on FA2 (gather) costs 1.41× per step
(4.85 s against 3.45 s), which still leaves about 1.2× more examples per second. Peak memory holds at 1.00× on both. Building the trees adds dataset maps on top of tokenization.
Attention
The collator (halo/data/collators/tree_packing.py) concatenates the batch's packed rows, recovers every
tree from two per-token columns (position along the token's own path, depth of its node) and puts the
index tensors each layer needs under the tree_attention batch key (halo/models/attention/tree_plan.py).
halo/models/attention/tree.py installs the readers on the family's own modeling module; nothing else in
the model changes. A flash softmax layer runs the stock packed path on a batch with no branch.
- Sliding-window layers gather, per tree node, the last
sliding_window - 1prefix tokens ahead of the node's own. FlashAttention aligns the causal mask bottom-right when a sequence has more keys than queries, which is "the prefix, then yourself causally". - Full layers,
split(default): the stock packed call runs over every node, and one rectangular pass per parent lets its children attend the prefix. The two partial softmaxes merge through their log-sum-exps. No key is copied per branch, and tokens outside any branch are bit-identical to flat packing. Needsflash_attention_4, the one backend that returns the log-sum-exp with a gradient. - Full layers,
gather: one key sequence per node, the whole prefix ahead of it. Runs on FA2 as well; the gathered keys grow with fan-out × prefix length, so a layer whose row gathers more than 2^19 keys (GATHER_KEYS_PER_CALLinhalo/models/attention/tree_plan.py) attends in several calls of whole nodes. That bounds the GQA backward, which expands key and value gradients to every query head. - GatedDeltaNet and KDA layers (Qwen3.5/3.6, GLM-5 Next): the causal convolution runs each node
behind the last
linear_conv_kernel_dim - 1tokens of its path, and the delta-rule recurrence runs one tree depth at a time, each node starting from its parent's final state. Each scan input is permuted into depth order once and every depth reads a view of it, so the backward is one inverse permutation per input instead of a gather's zero-filled, scattered gradient per depth. The plan carries each depth's varlen bounds as host integers as well, which reach fla ascu_seqlens_cpu, so building its chunk indices costs no host sync per depth and layer. - DeepSeek sparse attention layers (GLM-5 Next) read the plan in their own forward
(
halo/models/attention/tree_sparse.py), never at the attention interface:- Pools. The indexer's pools of
index_kpooltokens run along each token's own path: a pool is a token and its predecessors there. The pool straddling a branch point is one pool per branch. - Selection. A query's candidates are the pools whose last token precedes it on its path, plus
the incomplete pool it sits in. The indexer takes no gradient, so it is scored a chunk of queries
at a time; the stock form holds
[T, heads, T / index_kpool]fp32 scores. A tie at the cut goes to the earlier pool on the path. - Attention. It runs on the MLA latent, with the key projection folded into the query and the
value projection applied after, so a query reads only its selected latent rows. Under autocast it
reads the folded query and the latent in the autocast dtype and keeps its fp32 scores outside
autocast. The fold reads
kv_b_proj's weight and takes no dropout, so an adapter onkv_b_proj, a quantized load and a training-timeattention_dropoutare refused before the model loads: from the config (itsquantization_configincluded), the run'sload_in_4bit/load_in_8bit, and fromlora_target_moduleswhere it nameskv_b_proj(orself_attn.kv_b_proj) or isall-linear. The first tree batch checks the loaded layers again, which catches a regex target. - Plain documents. The plan's
sparsepart (per token: path predecessor, subtree end, path position, tree start) comes with every batch, so plain documents in one packed row stay apart in these layers too.
- Pools. The indexer's pools of
tree_full_attention left unset takes split where the model's backend runs it and gather elsewhere: on
flash_attention_2, and on FA4's head_dim-256 kernel, which takes no log-sum-exp gradient. Qwen3.5/3.6 takes
gather: on Blackwell an unset attn_implementation resolves to flash_attention_2, its packed-row default
(Qwen3.5), and its GatedDeltaNet layers need the fla and causal_conv1d kernels
the images ship. On Hopper, pin flash_attention_2: auto-selection picks FA3, which tree packing refuses. The
backend is checked before any weight loads, against the one the loader resolves for the config, dtype and GPU, and
again on the loaded model. GLM-5 Next is held to none of these backends and refuses tree_full_attention:
under a plan neither of its layer types reaches the attention interface. Its KDA layers need the same fla and
causal_conv1d kernels.
The split form and the state-passing recurrence add kernel variants to the
warm-up, compiled on every rank at startup of a multi-rank run.
Equivalence
Every example of a tree row is compared with the same example run completely alone. In fp32 on eager attention the per-example loss agrees to about 1e-5 and the argmax at every trained position is the same. In bf16 the difference is at the level of the backend's own noise — the yardstick column runs the unpacked examples through eager instead of the flash kernel:
Gradients are compared in fp32: in bf16, two attention backends already disagree on input-embedding
gradients by more than a defect would move them. With the whole model in fp32, Triton dots in IEEE
precision (TRITON_F32_DEFAULT=ieee, FLA_TRIL_PRECISION=ieee) and an exact torch varlen kernel
standing in for flash attention, the examples of real trees agree with their runs alone in loss and in
every argmax, and their input-embedding gradients to rounding; detaching the delta-rule state passed
between depths moves the shared tokens' gradients by orders of magnitude more. The residual is fp32
rounding of equivalent kernels, not the tree: each example run alone through the tree path, with no cut
and no sharing, moves its gradients just as much, while cutting a path into nodes and sharing a prefix
each add a few percent of that. Against a float64 recurrence, fla's delta rule cut in two with the state
handed over, and the causal convolution split at a seq_idx boundary, are as exact as one call.
A gather split into several calls gives the one-call forward bit for bit in fp32. Two bf16 forwards of the same row already differ, so chunked and one-call bf16 runs agree only to that level.
A tree row read as one causal sequence agrees at 69% on Qwen3.5-35B-A3B. That never runs: a
truncated, split or reordered tree row raises at collation, and a model whose layers would not read
the tree_attention key is refused at startup.
tests/cpu/data/test_tree_rows.py holds the data path to this (tree and flat packing of one dataset
yield the same examples and labels). tests/cpu/models/test_tree_attention_oracle.py and
tests/gpu/kernels/test_fa4_tree_attention.py hold the forward and gradients of every admitted flash
family. tests/cpu/models/test_tree_sparse_attention.py holds GLM-5 Next's: every example of a tree row
against its run alone, the selection against the stock indexer on every path, and the latent attention
against the dense masked softmax; tests/gpu/kernels/test_tree_sparse_attention.py its CUDA kernels. Both CPU
suites train a tree row of every admitted family under gradient checkpointing, reentrant and not, to the
logits and gradients of the run without it.
tests/gpu/data/test_tree_packing_e2e.py trains Qwen3-0.6B both ways through scripts/training/sft.py under
FSDP2 on two ranks, each step one whole epoch, and holds the tree run's per-step loss and gradient norm to the flat
run's.
What differs from flat packing
- Steps per epoch. A packed row holds more examples, so an epoch has fewer optimizer steps and each step more trained tokens. The learning-rate schedule spans fewer steps.
- Counters.
num_input_tokens_seenand tokens/s count each stored token once. Throughput in stored tokens/s is that of flat packing; examples/s is higher by the sharing factor. The MFU attention term costs each node's own tokens at its path's length, so a shared prefix is costed once. eval_loss. Each eval step's loss is token-weighted over that step's rows and the steps are averaged, so the value depends on which rows share a step. A tree run and a flat run of one model report different numbers on a small eval split while every example's loss is the same.- Router balancing.
bias_updatecounts a token once per example it belongs to, the load flat packing sees. Theaux_lossterm is computed over stored tokens, so a shared token weighs once in that regularizer instead of once per example; the language-model loss is unaffected. The MoE load metrics (enable_moe_metrics) count stored tokens too. - Disk. The token caches hold four columns, about 10 bytes per token against flat packing's 5.
Limits
tree_packing raises unless packing: true with packing_strategy: bfd (the other strategies cut a
row below a tree), eval_packing is left on and train_on_completions_only is on. It is refused
under context, tensor and pipeline parallelism, with torch_compile, with train_sinks, on a
pre-processed dataset and on the VLM path. The other tree_* options raise when set without it.
Expert parallelism and FSDP2 data parallelism never slice a row, so both admit tree rows. The end-to-end test is
FSDP2 on Qwen3-0.6B, and Qwen3.5-35B-A3B ran 5 steps of tree rows at ep8 on FA2 (gather). Pure ETP and EP+ETP are
admitted.
Families are admitted one by one (TREE_FAMILIES in halo/models/attention/tree.py), each by passing
the per-example oracle test; every other family is refused before the model loads. Backends are admitted
the same way, by the GPU kernel test: flash_attention_3 is refused. GLM-5 Next additionally refuses an
adapter on kv_b_proj, a quantized load and a training-time attention_dropout, before the model loads (see
Attention).
Source on GitHubUpdated 18 November 2026