draft-trees
Draft trees
The drafter keeps its runner-up guesses as branches of a tree, one pass of the full model checks every branch, and the round keeps the longest path it agrees with.
The problem
- A chain of drafts follows the drafter's first choice at every step, so one wrong guess ends the round even when its second choice was right.
- At batch size 1, a pass of the full model over a few dozen tokens costs about as much as a pass over one.
How it works
- Starting from the last token as the root, the drafter adds its best few next tokens, then keeps expanding the likeliest paths of the newest depth. Each node is scored by the draft probability of its whole path.
- The likeliest nodes of all depths are kept, 7 here. A child is never likelier than its parent, so every kept node keeps its parent.
- One pass of the full model reads every node. A mask lets each node attend only to the text so far and its own ancestors, and the pass predicts the next token after every node.
- The walk starts at the root and moves to the child holding the model's prediction, emitting it. Where no child matches, the prediction itself is emitted, as the correction or as a bonus at a leaf.
- The keys and values the pass wrote for the accepted nodes move to the front of the cache in order, and the other rows are dropped.
Configuration
Its options, set per engine in configuration.json. Each is checked against its type and range when the engine loads.
| Option | Default | Values | What it sets |
|---|---|---|---|
depth | 4 | int 1 to 16 | Depths the tree grows past the pending token |
branch | 3 | int 1 to 16 | Children each expanded node gets: the drafter's best next tokens |
beam | 3 | int 1 to 16 | Likeliest paths of the newest depth expanded at the next one |
configuration.json
{"plugins": {
"use": {"drafter": "draft-trees", "verifier": "draft-trees"},
"options": {"draft-trees": {"depth": 4, "branch": 3, "beam": 3}}
}}Pays off when
- The drafter's first choice is often wrong where its second or third is right, as with MTP layers and other small drafters.
- One request at a time, where the extra columns of a tree cost little in the verifying pass.
Doesn't pay off when
- Many requests are batched and the pass is bound by compute, so every extra node costs real time.
- The model has recurrent layers (gated delta, Mamba). Their state depends on the path, so every node would need a state of its own.
What must stay true
- Parents come before children, and each node's mask is exactly its path from the root.
- Each node is predicted from exactly its own path, at the position its depth gives it, so siblings share a position.
- Every emitted token is the full model's own choice (its argmax, or its own draw when sampling), so a tree changes how many tokens a round emits, never which.
- Accepted rows move in increasing order, so no move overwrites a row a later move still reads.
crit-hub