LLM dev¶

Dynamic programming (DP) is an algorithmic technique that turns an exponential-size search into a polynomial-size computation by exploiting two properties:

Optimal-substructure – Any optimal solution is composed of optimal solutions to smaller sub-problems.
Overlapping sub-problems – The same sub-problems appear again and again, so we memoize (cache) their answers instead of recomputing them.

The procedure in Algorithm 1 is a textbook application of DP on a tree, where the “sub-problem” solved at each node is:

“Given the subtree rooted at this node, what is the best way to fork/merge so that the first-level token reuse (the reuse of tokens that appear immediately under the current node) is maximized?”

1. The tree structure and the meaning of “prefixes”¶

The document describes a prefix tree (trie) of tokens (words or sub-words).
A node D represents a prefix (sequence of tokens).
First-level prefixes of D are exactly the tokens labeling the edges from D to its children.
Reusing a first-level prefix means that two different children of D share the same token label.

Example:
D
/ \
A A ← first-level token “A” reused once.

2. The recursive structure (optimal substructure)¶

1
2
3

function MaximizeReuse(D)
  if D has no children then
    return

Base case: A leaf node has no children, hence no first-level prefixes to reuse.
Inductive step: The optimal way to maximize reuse in the subtree rooted at D is computed after we already know the optimal way for every subtree rooted at D.children (hence the recursive call).

3. Bottom-up processing order¶

1 2	`for child ∈ D.children do MaximizeReuse(child) // Solve sub-problems`

This is post-order traversal: children are solved first, then their parent.
The memoized result for each child is the best configuration of forks and merges inside its own subtree.

4. The local decision at node `D`¶

For every grand-child gchild of D (i.e., a child of a child):

1 2	`gain ← (leaves(gchild) - 1) × tokens(gchild) penalty ← tokens(child)`

Gain estimates how many tokens we save if we reuse gchild’s token sequence:
– leaves(gchild) is the number of leaf nodes (final completions) that pass through gchild;
– (leaves(gchild) - 1) is the number of extra times we can reuse the same token sequence;
– tokens(gchild) is the length (in tokens) of that sequence.
Multiplying them gives total saved tokens.
Penalty is the cost of creating the fork (duplicating the child’s prefix).

1 2	`if gain > penalty then Fork child and merge with gchild`

This is the Bellman principle in action: we perform the fork/merge only if the local gain outweighs the local penalty, because any later decisions higher up the tree will inherit this local optimum.

5. Memoization (implicit)¶

Although the pseudocode does not show an explicit table, the recursion plus the post-order traversal effectively memoize the best reuse configuration for every subtree. Once a child’s subtree has been processed, its internal structure is frozen; future computations higher up the tree treat that child as a black box that already maximizes reuse within its own subtree.

6. Overall DP complexity¶

Let

n = number of nodes in the tree,
k = maximum branching factor.
Each node is visited once.
At each node we examine at most k children and, for each child, at most k grand-children → O(k²) work per node.

Hence the algorithm runs in O(n k²) time and O(n) memory (the recursion stack + memo).

7. Intuition in one sentence¶

Dynamic programming here means: “Solve the token-reuse problem for every subtree bottom-up, cache the answer, and at each parent node decide whether to glue two smaller optimal subtrees together if it yields net token savings.”