# DMSD Horizon Edition v0.7
## Algorithm Portfolio / Auto-Router

**日期：** 2026-09-30  
**狀態：** COMPLETE  
**基礎：** v0.6 Cross-Algorithm Competition  
**核心：** 讓 Horizon runtime 自動決定「何時相信既有 calibration、何時切換演算法、何時需要重新 microbenchmark」。

---

# 1. 從 Static Map 到 Adaptive Router

v0.6 已經有：

\[
\boxed{
\text{Measured Winner}
+
\text{Crossover}
+
\text{Pareto Split}.
}
\]

但真正 runtime 不能只看靜態表。

因為：

- runtime noise 會改變 tiny crossover；
- environment 會漂移；
- input 可能落在 calibration range 外；
- memory gate 可能直接淘汰最快演算法；
- 某些 algorithm 可能當下不可用。

所以 v0.7 定義：

\[
\boxed{
\Pi_{\rm route}(Q,x,R,E,\mathcal C)
\to
(A,\text{state},\Gamma)
}
\]

其中：

- \(Q\)：task；
- \(x\)：problem size；
- \(R\)：resource constraints；
- \(E\)：environment；
- \(\mathcal C\)：calibration registry；
- \(A\)：selected algorithm；
- \(\Gamma\)：routing provenance。

---

# 2. Router Pipeline

正式 pipeline：

```text
1. semantic compatibility
2. implementation availability
3. hard resource admission
4. calibration/trust lookup
5. crossover proximity check
6. model ranking
7. optional microbenchmark
8. robust local calibration
9. final routing decision
10. provenance append
```

這個順序很重要。

例如：

\[
\boxed{
\text{resource admission}
}
\]

一定要先於：

\[
\boxed{
\text{fastest-time selection}.
}
\]

否則會選出根本無法執行的算法。

---

# 3. Routing States

v0.7 註冊：

```text
SAFE_MEASURED
NEAR_CROSSOVER
OUTSIDE_CALIBRATION
RESOURCE_FORCED
MICROBENCH_REQUIRED
MICROBENCH_UPDATED
LOCAL_CALIBRATION_APPLIED
NO_ADMISSIBLE_ALGORITHM
```

每個 state 的語義不同。

---

# 4. SAFE_MEASURED

若 requested size：

- 落在 measured range；
- 不靠近 crossover；
- resource gates 通過；

則直接使用 calibrated winner。

例：

### Certificate 30 relations

\[
A^*=\texttt{python\_scalar}.
\]

### Certificate 100,000 relations

\[
A^*=\texttt{numpy\_vectorized}.
\]

### Sieve \(N=10^6\)

\[
A^*=\texttt{odd\_only\_bytearray}.
\]

---

# 5. RESOURCE_FORCED

若最快算法不通過 resource gate，
router 不需要等到 time curve crossover。

例如：

\[
N=10^7
\]

prime-count query，

若 memory budget：

\[
100,000\text{ bytes},
\]

則：

```text
full_bytearray: rejected
odd_only:       rejected
segmented_64k:  admitted
```

因此：

\[
\boxed{
A^*=\texttt{segmented\_64k}
}
\]

state：

\[
\boxed{
\texttt{RESOURCE\_FORCED}.
}
\]

---

# 6. Memory Objective

甚至沒有 hard budget 時，
若 objective 是：

```text
minimize memory
```

在 \(N=10^7\)：

router 也會選：

\[
\boxed{
\texttt{segmented\_64k}.
}
\]

所以 algorithm router 不應只有：

\[
\text{time objective}.
\]

它必須能根據 task policy 選：

- time；
- memory；
- energy；
- confidence；
- cost。

---

# 7. OUTSIDE_CALIBRATION

若：

\[
x>x_{\max,\rm measured},
\]

不能把 extrapolated fit 當 measurement。

router 先標：

\[
\boxed{
\texttt{OUTSIDE\_CALIBRATION}.
}
\]

如果 local probe：

- 安全；
- 便宜；
- 有 compatible implementation；

才允許：

\[
\boxed{
\text{microbenchmark}.
}
\]

---

# 8. Sieve 外插案例

v0.6 最大 sieve measured point：

\[
10^7.
\]

v0.7 query：

\[
2\times10^7.
\]

原 local model 預測：

```text
odd-only:  ~0.0439 s
segmented: ~0.1801 s
```

router 判定：

```text
outside measured range
but probe cheap enough
```

所以現場量測。

得到：

```text
odd-only:  ~0.0830 s
segmented: ~0.1662 s
```

模型低估了 odd-only 的絕對時間，
但：

\[
\boxed{
\text{winner identity remained correct}.
}
\]

因此 route：

\[
\boxed{
\texttt{MICROBENCH\_UPDATED}
\to
\texttt{odd\_only\_bytearray}.
}
\]

---

# 9. GEMM Outside Calibration

v0.6 GEMM measured 到：

\[
n=48.
\]

v0.7 probe：

\[
n=64.
\]

model：

```text
OpenBLAS ~9.69 µs
Python naive ~10.60 ms
```

local measurement：

```text
OpenBLAS ~11.81 µs
Python naive ~13.02 ms
```

winner：

\[
\boxed{
\texttt{numpy\_openblas}.
}
\]

即使絕對預測有誤差，
algorithm identity 非常穩定。

---

# 10. Bigint Outside Calibration

v0.6 measured 到：

\[
512\text{ limbs}.
\]

v0.7 probe：

\[
1024\text{ limbs}.
\]

model：

```text
schoolbook ~81 ms
Karatsuba ~30.6 ms
CPython native ~7.34 ms
```

local measurement：

```text
schoolbook ~103.7 ms
Karatsuba ~37.9 ms
CPython native ~10.1 ms
```

winner identity：

\[
\boxed{
\texttt{cpython\_native\_bridge}.
}
\]

---

# 11. Custom Bigint Stable Crossover

如果 native runtime 不可用，

只保留：

```text
schoolbook
Karatsuba
```

在：

\[
256\text{ limbs}
\]

router 會 local probe。

結果：

```text
schoolbook ~5.80 ms
Karatsuba ~3.76 ms
```

所以：

\[
\boxed{
\texttt{karatsuba\_limbs}
}
\]

與 v0.6 stable crossover 一致。

---

# 12. 最重要的新問題：Microbenchmark 自己也有 Noise

v0.6 historical certificate crossover：

\[
\boxed{
\sim94.99\text{ relations}.
}
\]

v0.7 第一次在：

\[
95
\]

relations 做單次 local probe，
曾得到：

```text
scalar faster
```

但稍後同點重測又得到：

```text
vectorized faster
```

因此：

\[
\boxed{
\text{single microprobe}
\neq
\text{persistent calibration update}.
}
\]

這是本輪最重要的新發現。

---

# 13. Provisional Probe

v0.7 因此把：

```text
one local benchmark
```

只視為：

\[
\boxed{
\texttt{PROVISIONAL}.
}
\]

它可以：

- 幫當前 query 做決策；

但不能：

- 覆蓋歷史 calibration；
- 永久改 crossover；
- 宣稱 environment 已穩定轉移。

---

# 14. Robust Local Calibration

certificate crossover 改做：

```text
5 batches
× 7 repeats
per algorithm
```

每個 size 取：

\[
\text{median of batch medians}.
\]

測：

\[
60,80,90,95,100,110,130,160
\]

relations。

結果：

### 60

scalar faster。

### 80

幾乎相同：

\[
\frac{T_{\rm scalar}}{T_{\rm vector}}
\approx0.989.
\]

### 90

vectorized 已勝：

\[
\approx1.120.
\]

---

# 15. Updated Local Crossover

log-ratio interpolation：

\[
\boxed{
C^*_{\rm local}
\approx80.85\text{ relations}.
}
\]

historical：

\[
94.99.
\]

local robust：

\[
80.85.
\]

所以：

\[
\boxed{
\text{crossover itself is environment/time-local}.
}
\]

而不是 universal constant。

---

# 16. Historical Calibration 不被覆寫

v0.7 不會把：

```text
94.99
```

刪掉改成：

```text
80.85.
```

而是：

```text
historical calibration:
  ~94.99

local environment overlay:
  ~80.85

state:
  LOCAL_CALIBRATION_APPEND
```

這保留：

\[
\boxed{
\text{provenance}.
}
\]

---

# 17. Hysteresis

如果兩 algorithms：

\[
\frac{T_A}{T_B}
\]

太接近 1，
router 不應頻繁切換。

v0.7 建議第一版 hysteresis band：

\[
\boxed{
|T_A/T_B-1|<0.15.
}
\]

在這個區間：

```text
keep both candidates
request more samples
or retain current stable policy
```

而不是每一次 µs noise 都 flip。

這個 15% 是 runtime policy parameter，
不是數學定理。

---

# 18. Robust Certificate Policy

經 local overlay：

```text
relations < ~81:
    python_scalar

relations > ~81:
    numpy_vectorized
```

但 near band：

```text
~70–95
```

仍可以：

```text
microbenchmark / hysteresis
```

而不是把：

\[
80.85
\]

當 hard universal boundary。

---

# 19. Measured Winner Replay

v0.7 把 v0.6 所有 measured points 重新丟進 router，
不允許 microbenchmark。

總計：

\[
\boxed{
32
}
\]

個 measured-size routing checks。

全部：

```text
router selected measured winner
```

PASS。

---

# 20. Microbenchmark Winner Replay

v0.7 實際觸發：

- certificate crossover；
- sieve extrapolation；
- GEMM extrapolation；
- bigint measured-near-crossover；
- bigint custom crossover；
- bigint extrapolation。

共：

\[
\boxed{6}
\]

個 microbenchmark decisions。

每次 provisional route 都選：

\[
\arg\min
T_{\rm local}.
\]

全部 PASS。

---

# 21. Model Winner vs Local Measurement

經 robust certificate resolution 後，
這 6 個 microbench cases：

```text
predicted winner == locally measured winner
```

全部一致。

所以：

\[
\boxed{
6/6
}
\]

winner identity correct。

這不是說 time model 完美。

只是說在這組測試中：

\[
\boxed{
\text{ranking prediction}
}
\]

比：

\[
\boxed{
\text{absolute runtime prediction}
}
\]

更穩定。

---

# 22. Router 信任階層

v0.7 暫定：

## Level 0 — Exact current measurement

requested point 就有 measurement。

## Level 1 — Interpolation

位於兩個 calibrated points 間。

## Level 2 — Near extrapolation

剛離開 measured range。

## Level 3 — Far extrapolation

不能高信任使用。

## Level 4 — Local microbenchmark

對當前 environment 重新量。

## Level 5 — Robust local calibration

多 batch / local sweep。

這不是單純：

\[
\text{model score}.
\]

而是：

\[
\boxed{
\text{evidence hierarchy}.
}
\]

---

# 23. Microbenchmark Budget

microbenchmark 也不是免費的。

未來正式 policy 應有：

\[
B_{\rm probe}.
\]

只有若：

\[
\hat C_{\rm probe}
\le
B_{\rm probe}
\]

才允許 probe。

因此 Auto-Router 本身也成為一個：

\[
\boxed{
\text{meta-budget problem}.
}
\]

它要決定：

> 為了選算法，值得花多少時間先量算法？

---

# 24. Value of Information

如果兩 algorithms 預測差距非常大：

```text
A: 10 µs
B: 10 ms
```

沒有必要 microbenchmark。

但若：

```text
A: 4.2 µs
B: 4.3 µs
```

probe 的 information value 很高。

所以 future router 可估：

\[
\boxed{
VOI_{\rm probe}
=
\text{expected routing loss avoided}
-
\text{probe cost}.
}
\]

v0.7 先用：

```text
near crossover
outside calibration
```

作簡單 proxy。

---

# 25. Local Calibration Overlay

正式引入：

\[
\boxed{
\mathcal C_{\rm local}
}
\]

它：

- 有 environment scope；
- 有 timestamp；
- 有 method；
- 有 raw samples；
- 不覆寫 global history。

Router 查 calibration 順序可為：

```text
local robust
↓
local provisional
↓
historical measured
↓
interpolated
↓
extrapolated model
```

---

# 26. Auto-Router State

完整 decision：

\[
D
=
(
Q,
x,
R,
A,
K,
P,
M,
\Gamma
)
\]

其中：

- \(Q\)：task；
- \(x\)：size；
- \(R\)：resources/objective；
- \(A\)：selected algorithm；
- \(K\)：routing state；
- \(P\)：prediction evidence；
- \(M\)：microbenchmark evidence；
- \(\Gamma\)：provenance。

---

# 27. Final Routing Examples

### cert_tiny

```text
SAFE_MEASURED
→ python_scalar
```

### cert_cross

```text
near crossover
→ provisional probe noisy
→ robust local sweep
→ LOCAL_CALIBRATION_APPLIED
→ numpy_vectorized
```

### sieve_out

```text
OUTSIDE_CALIBRATION
→ cheap local probe
→ odd_only_bytearray
```

### sieve_mem

```text
RESOURCE_FORCED
→ segmented_64k
```

### gemm_out

```text
OUTSIDE_CALIBRATION
→ microbenchmark
→ numpy_openblas
```

### bigint_custom_cross

```text
NEAR_CROSSOVER
→ microbenchmark
→ karatsuba_limbs
```

---

# 28. Auto-Router 與 Horizon 的關係

以前 compute horizon：

\[
H_{Q,A}.
\]

現在：

\[
\boxed{
H_Q
=
\sup_x
\left[
\exists A\in\mathcal A_Q:
\Pi_{\rm route}(Q,x)\text{ admits }A
\right].
}
\]

因此 Horizon 不再綁死一個 algorithm。

它可以：

\[
\boxed{
\text{隨尺度改 algorithm}.
}
\]

---

# 29. Validation

v0.7：

```text
32 measured winner replay checks
1 hard resource-gate check
6 microbenchmark-minimum checks
2 robust crossover sign checks
```

全部：

```text
PASS
```

robust resolution 後，
microbenchmark cases 的 predicted winner：

\[
\boxed{
6/6
}
\]

與 local measured winner 相同。

---

# 30. 下一步

下一輪可以做：

# Horizon Edition v0.8 — Online Calibration Memory / Learning Router

現在 local calibration 還只是：

```text
當前 session overlay.
```

下一步可以加入：

- environment fingerprint；
- calibration cache；
- decay / staleness；
- runtime drift detection；
- sample reuse；
- confidence interval；
- change-point detection；
- active benchmark scheduling。

也就是：

\[
\boxed{
\text{Auto-Router}
\rightarrow
\text{Learning Router}.
}
\]

---

# 31. 結論

v0.7 最重要的不是「自動選最快」。

而是建立：

\[
\boxed{
\text{知道何時不該相信自己的舊 calibration}
}
\]

的 runtime。

真正的流程變成：

\[
\boxed{
\text{predict}
\rightarrow
\text{admit}
\rightarrow
\text{measure when valuable}
\rightarrow
\text{update locally}
\rightarrow
\text{route}
}
\]

而不是：

\[
\text{hard-code crossover}.
\]

---

```text
DMSD Horizon Edition v0.7: COMPLETE
Portfolio Router: ENABLED
Local Microbenchmark: ENABLED
Robust Local Calibration: ENABLED
Historical Provenance: PRESERVED
Validation: PASS

Next:
v0.8 — Online Calibration Memory / Learning Router
```