Experiment: qualify shared-prefix tree verification and conservative admission #728

This issue tracks experimental draft PR #727 and the conservative tree admission experiment. Keep tree verification default off. The earlier default-on question below is historical, not the current proposal.

Experimental tree verification — default off

Related issue #728. Keep this PR in draft; do not enable the default. This updates the existing tree PR instead of duplicating it. The earlier two measured improvements remain separately tracked in #756 and #757.

Reference: Muse Spark Open Ultrafast: Pushing beyond 1,000 Tokens per second, specifically shared-prefix speculative tree verification. The article’s CUDA/GB300 measurements are not a Metal/M5 baseline.

The opt-in native path verifies sixteen unique shared-prefix candidate nodes from the existing trained eight-row draft, then retains the selected target path and its GDN/attention state. Eligibility remains a single dense 5120-hidden target (tested Qwen3.8-27B 4-bit), fp32 GDN state and Int8 KV, without penalties, images, constraints or thinking. Other requests use the chain path. This is research code, not a generally qualified model/runtime optimization.

The latest change preserves all fixes in 35e5bf21a07f9012a0a575b9d5d1ab95cdbce19f (desktop options, current server fixtures, argument/sampling tests and architecture cleanup). It changes the initial retained-token average from four to the maximum eight rows. The 6.5 threshold and 0.125 EMA update weight are unchanged: observe chain acceptance before paying for wider work. It also adds a reproducible same-Engine benchmark and frozen twelve-prompt token cohort.

Current branch validation

• Production/native builds, make check-native-cpu, build identity verification and architecture validation pass. Engine size is 30,104 lines against the unchanged 30,105 budget. No budget or exception was raised. Python lint/format and patch whitespace checks pass.
• The committed benchmark on e5c3c323f96ba5bdbad7940e427a100e55fdfd8f passes all twelve cold greedy prompts × four samples under Metal shader validation: complete output arrays and cache metadata match, with 90 observed wide cycles and zero wide cycles in chain arms. The subsequent runner-only change permits output directories outside the checkout; it does not alter instrumentation or model execution.
• This is not a new sampled-distribution, restored/branching conversation, active mixed-tree batch, long-context, 35B/MoE, or HTTP serving qualification. Default remains off.

Current source timing

Measured source e1f91e4ffb58bf561562aa2eba3f6e789e11c2ef, with the committed benchmark. Forty samples per prompt, first eight excluded from timing only; eight alternating balanced blocks remain. All twelve full output/cache groups match; 920 observed wide cycles. Geometric mean of per-prompt whole-request tokens/sec changes: +4.23%.

Aggregate metric verdicts: {'pass': 36}. Individual block verdicts: {'pass': 282, 'fail': 4, 'inconclusive': 2}. All blocks are retained, including failures/inconclusive results; no TTFT benefit is claimed. Raw JSON SHA-256: 57ea29b6459f1c947804c71b071e5636b247e88e30409e6f1fc29a7b705cdc74.

The original six screen prompts give +8.60%; the six structured prompts give +0.03%. These are repeat measurements of the frozen cohort, not a new independent holdout.

Earlier controlled experiments (different source revision)

Measured tree source a8795e3d960b389a80f659ce34f62fff6c3918eb, based on attention-layout commit c4038a1a520bc490b5ecec7e6440c8252b3fd9ba (PR #756). Both arms shared that port’s setup/cache writer-retention policy. Only tree execution toggled. These results do not describe an unmodified-main comparison, an HTTP benchmark, additive gains with #757, or the exact current PR head.

The initial four-row prior lost 3.89% on counting (96.63 → 92.87 tokens/sec): both arms accepted 55 proposals in nine cycles, but the tree evaluated 102 nodes instead of 62. This failure motivated freezing the conservative eight-row prior and cohort before the next measurements. With the new rule, counting B1–B4 stayed on the chain and was within 0.29%.

Twelve cold greedy prompts capped at 96 tokens, 40 samples each (8 excluded from timing only, then 8 alternating ABBA/BAAB blocks): geometric mean request tokens/sec +4.42% overall, +9.04% for six screen prompts, +0.0035% for six structured holdout prompts. The holdout shows neutral fallback, not an independent positive gain. All aggregate wall/TTFT/GPU comparisons passed; individual metric blocks were 277 pass / 10 inconclusive / 1 fail. The failed SQL TTFT block was +2.67% against a 2.16% bound and is retained. An independent SQL repeat passed all eight TTFT blocks (132.747 → 132.420 ms, −0.25%). No TTFT gain is claimed.

Earlier shader evidence at a8795e3d: 580 exact raw target-argmax checks / 59 wide cycles, six complete arrays matching the untouched reference. Pathwise GDN oracles passed 108 cases per mode (pending 0–8, two layers, flat/tiled head order, three trees; all 10,616,832 hidden values plus state/tape/guards exact). Attention oracles passed 54 cases per mode (histories 0–8192, two split choices, three trees, all 16 nodes/24 heads/D256; 5,308,416 BF16 outputs and mapped FP32 partials/statistics exact; 2,112 FP64 samples pass). Those operator implementations are unchanged here, but these are earlier runs, not freshly repeated current-head oracle certificates.

The borrowed attention fixture initially omitted residency declarations through its raw-pointer KV-table writer, causing both reference and candidate to return zeros under validation. Switching the fixture to the typed writeTable(pages, table) registered the addressed buffers. No kernel, tolerance or test case was relaxed; the original failure is retained locally. The old prototype’s 30,128-line engine architecture failure is also historical; the preserved later branch fixes now pass at 30,104.

Reproduce and interpret

M5 Pro (20 GPU cores, 48 GB), macOS 26.6, Apple clang 21 / Metal 4.0, macOS deployment target 26.4. Public target revision 10c35caafbb80f7dc6a7a432cdd11af10a6d4818.

python3 dev/benchmarks/experiments/tree_verify/run.py --model /path/to/Qwen3.8-27B-4bit --shader-validation --output build/experiments/tree-verify/shader
python3 dev/benchmarks/experiments/tree_verify/run.py --model /path/to/Qwen3.8-27B-4bit --output build/experiments/tree-verify/normal

The benchmark links generated instrumentation ahead of the runtime library, forces all draft rows, disables ANE sharing and keeps default int8 activations. Both arms keep the same tree-capable setup/cache writer policy; the per-request execution gate is the only treatment. Every sample checks complete output arrays and cache metadata. Whole-request tokens/sec includes prefill; it is not decode-only throughput. The cohort is a repeat of the original prompts, not a new holdout.

The unchanged repository ABBA rule declares spread >5% inconclusive, otherwise permits regression up to max(2%, twice spread). A pass means non-regression, not a demonstrated gain. Raw output, per-request progress, every metric block, source/binary/model identities and hashes remain in ignored build/experiments/tree-verify/; the runner reproduces them. Model weights are not included.

Companion experiments (also drafts): larger attention fusion #759 / #761; GPU ready-queue scheduling #760 / #762. Their regressions are retained; neither is integrated into the production runtime. Full-layer megakernels and a full GPU VM remain unimplemented; testing these components does not exhaust every idea in the article.

Hosted CI status

Current Actions run is not green. The production job fails during xcodebuild -downloadComponent MetalToolchain, before project compilation: Apple’s Metal toolchain asset catalog could not be fetched (exit 70). Local validation above passed independently. Other hosted jobs may still be running; no hosted all-checks-pass claim is made.