Skip to content

algorithm.md

Latest commit

 

History

History
115 lines (71 loc) · 4.91 KB

algorithm.md

File metadata and controls

115 lines (71 loc) · 4.91 KB
Raw

Algorithm notes

This repository is a mechanism-level CPU reference lab, not the upstream DFlash inference engine. It compares eight decoding paths under one deterministic workload.

1. Normal autoregressive decoding

For each output token the target SLM runs on the visible sequence, chooses the greedy next token and appends it.

2. DFlash reference mode

A small non-causal drafter predicts all positions of a future block in one forward pass. The target verifies the block, accepts the matching prefix and corrects the first mismatch.

3. DFlash v2 reference mode

The DFlash2-style selector retains top-k candidates at every position and uses learned predecessor-conditioned transition scores with dynamic programming. Guidance work is approximately:

K + (B - 1) * K^2

or O(BK²).

4. DFlash3-MOBS

MOBS chooses a central anchor and expands left/right, scoring only K candidates against already selected neighbors. With a fixed number of refinement passes its selector work is O(BK).

5. DFlash4-JUMP-MOBS

A separately trained jump head predicts sparse future anchors, then O(BK) local gap filling constructs the complete path. Its measured CPU weakness is the extra jump-head forward pass.

6. DFlash5-FUSED-JUMP-MOBS

DFlash5 reuses existing drafter hidden states and applies a low-rank residual only to retained top-k candidates at sparse offsets. It removes DFlash4's separate jump-forward pass while preserving exact target verification.

7. DFlash6-Boltzmann

DFlash6-Boltzmann is deliberately training-free. It uses only the draft logits already computed by DFlash.

Candidate distribution

At each position it retains the drafter's top-k candidates. For candidate c with draft logit z(c) it conceptually samples from:

P(c) ∝ exp(z(c) / T_i)

The implementation uses deterministic Gumbel-Max:

score(c) = z(c) / T_i + gumbel(context, position, token_id)

The Gumbel value is generated by a deterministic SplitMix64-style hash, so there is no mutable RNG state and the benchmark remains reproducible.

Adaptive temperature

Temperature is reduced when the drafter is already confident. With margin

m_i = top1_logit - top2_logit

the reference implementation uses an exponentially decreasing effective temperature:

T_i = max(T_base * exp(-m_i), 0.02 * T_base)

Thus high-margin positions approach ordinary DFlash argmax, while uncertain positions receive more exploration.

Complexity

The implementation evaluates deterministic Boltzmann scores only for the retained candidate set. For block length B and candidate width K, proposal-selection work is approximately O(BK), with no learned selector and no additional model forward pass.

8. DFlash6-BMOBS

BMOBS combines Boltzmann exploration with the previously tested middle-out linear selector.

  1. retain top-k candidates at every position;
  2. for an even block, compare the two central positions and choose the one with the smaller top-1/top-2 margin;
  3. use deterministic Boltzmann/Gumbel scoring to select one anchor candidate there;
  4. fill the remaining positions using the existing O(BK) adjacent-neighbor MOBS mechanism;
  5. pass the complete proposal to the exact target verifier.

This is designed to spend stochastic/exploration work at one uncertain middle anchor rather than sampling every slot.

Exactness

Boltzmann proposals are approximate and can be wrong. Neither DFlash6 mode emits them directly. The target model verifies the proposal and corrects the first mismatch, so tests compare each final greedy sequence with normal target-only decoding.

What the first DFlash6 benchmark found

The first full CI experiment selected base temperatures 0.35 for Boltzmann and 0.20 for BMOBS. Relative to plain DFlash on that runner:

  • Boltzmann increased acceptance by about 2.7 percentage points;
  • BMOBS increased acceptance by about 5.4 percentage points;
  • BMOBS approached DFlash2/MOBS target-pass efficiency with substantially less guidance work than DFlash2;
  • both remained slower in end-to-end CPU tokens/sec because candidate extraction, deterministic Gumbel calculations and (for BMOBS) neighbor scoring cost more than the verification work saved.

The repository intentionally preserves this result rather than claiming that better acceptance automatically means faster decoding.

Complexity summary

Normal:                 O(N) target passes for N output tokens
DFlash:                 parallel draft + target verification
DFlash2 selector:       O(BK^2)
DFlash3-MOBS:           O(BK)
DFlash4-JUMP-MOBS:      O(BK + JK) plus separate jump inference
DFlash5-FUSED-JUMP:     O(BK + JKR), no separate jump inference
DFlash6-Boltzmann:      O(BK), no learned selector/model pass
DFlash6-BMOBS:          O(BK), one Boltzmann anchor + linear fill

These statements describe path-guidance candidate scoring in this reference implementation, not total Transformer inference complexity.