# SDRPC-PRIME-001 Validation Phase I — Round 22
## Learned / Adaptive Kernel Heuristic

**日期：** 2026-09-23  
**Source graph：** Round 21 canonical kernel graph（896 nodes）

**作者：** Neo.K  
**機構：** EveMissLab／一言諾科技有限公司  
**版本：** 原稿未標註（本次整理版）  

---

## 1. 這輪不再改 Planner，而是改「剩餘距離估計」

Round 21 已經有 exact kernel-space planner，但 heuristic 幾乎沒有幫助：

```text
Uniform-Cost expanded 148 nodes
Round21 analytic A* expanded 147 nodes
```

所以 Round 22 問：

> 能不能從 kernel 本身的 geometry，預測「離 target-sufficient kernel 還有多遠」？

## 2. Learned Features

本輪 regression 使用：

```text
residual structure
log cross-label pairs
log kernel pairs
log block count
cross-label / kernel-pair ratio
inverse block count
equivalent probe-subset multiplicity
```

target 是 Round 21 graph 上的 exact cost-to-go。

訓練／測試以 kernel hash 做 deterministic 約 80/20 split。

**注意：這只是同一 graph 內的 held-out nodes，不是跨 domain generalization。**

## 3. Raw Learned Predictor：準，但不安全

Held-out：

```text
RMSE = 0.764
MAE  = 0.428
```

但 raw predictor 在 test nodes 上約：

```text
37.65%
```

會高估 exact remaining cost。

所以：

```text
predictive accuracy != admissibility
```

它不能直接作為保證 optimal 的 A* heuristic。

## 4. Goal-Zero + Calibration

我們先強制：

```text
h(K)=residual_mass(K) × predicted_cost_per_residual(K)
```

因此任何 goal kernel（residual=0）一定有：

```text
h(goal)=0
```

接著再做 safety calibration。

### Global scaling

單一 global scale：

```text
alpha = 0.042817
```

非常保守。

### Piecewise calibration

改按 residual-mass bins 分區，各自用全 graph exact cost-to-go 壓到不高估。

這是：

```text
graph-calibrated admissible heuristic
```

不是可直接跨 graph 使用的 theorem。

## 5. Hybrid Heuristic

最後：

```text
h_hybrid(K)
 = max(
     h_piecewise_learned(K),
     h_round21_analytic(K)
   )
```

兩者都在本 graph 上 admissible，因此 max 仍 admissible。

本輪全節點驗證：

```text
admissible = True
```

## 6. Consistency 是第三件不同的事

Hybrid heuristic 雖 admissible，但：

```text
consistent = False
max consistency violation = 1.672
```

所以 planner 不能假設 closed node 永遠不用重開。

本輪 A* 實作因此支援 improved-g reopen。

實際這張 graph 上：

```text
reexpanded events = 0
```

但安全性來自 planner 支援 reopen，不是因為碰巧沒發生。

## 7. Search 結果

| Heuristic / Search | Guarantee | Expanded | Discovered | Cost | Path |
|---|---|---:|---:|---:|---|
| UCS | optimal | 148 | 428 | 7.8 | `W210 → F3 → S2` |
| Analytic-A* | optimal / admissible+consistent | 147 | 426 | 7.8 | `W210 → F3 → S2` |
| Learned-GlobalScaled-A* | optimal / admissible; reopen-capable | 142 | 427 | 7.8 | `W210 → F3 → S2` |
| Learned-Piecewise-A* | optimal / admissible; reopen-capable | 133 | 401 | 7.8 | `W210 → F3 → S2` |
| Hybrid-Admissible-A* | optimal / admissible; reopen-capable | 132 | 399 | 7.8 | `W210 → F3 → S2` |
| Raw-Learned-Unsafe-A* | none from heuristic admissibility | 63 | 264 | 7.8 | `W210 → F3 → S2` |
| Exact-Oracle-A* | optimal but oracle reference | 11 | 81 | 7.8 | `W210 → F3 → S2` |

最重要的三個數字：

```text
UCS                     148 expanded
Hybrid admissible A*    132 expanded
Raw learned unsafe A*    63 expanded
Exact cost-to-go oracle  11 expanded
```

因此：

```text
safe learned/adaptive heuristic
```

已把 expansion 降約：

```text
10.81%
```

而未校準 model 顯示仍有大量潛在 search signal，但不能拿掉安全邊界。

## 8. Raw Unsafe 為什麼仍值得保留

Raw model 本輪碰巧仍找到 optimum：

```text
cost = 7.8
```

且只展開 63 nodes。

但這只是 observed outcome。

因為它會 overestimate，所以不能保證：

```text
first goal popped = optimal goal.
```

因此 raw model 更適合作：

- node ranking；
- tie breaking；
- candidate ordering；
- bounded / anytime search；

而不是無條件替代 admissible heuristic。

## 9. Weighted A*

使用 admissible hybrid heuristic，再把 heuristic 乘 weight：

| Weight | Expanded | Cost | Observed ratio to optimum | Formal search bound* |
|---:|---:|---:|---:|---:|
| 1.25 | 121 | 7.8 | 1.000 | ≤ 1.25× |
| 1.50 | 116 | 7.8 | 1.000 | ≤ 1.50× |
| 2.00 | 101 | 7.8 | 1.000 | ≤ 2.00× |
| 3.00 | 91 | 7.8 | 1.000 | ≤ 3.00× |

`*` 這裡的 bound 是 weighted A* 在非負 edge cost、admissible h、支援必要 reopen 的搜尋設定下的標準 bounded-suboptimal interpretation；本 graph 的 observed solutions 全部仍剛好是 exact optimum 7.8。

最激進的 `w=3`：

```text
expanded = 91
```

相對 UCS 減少：

```text
38.51%
```

但形式上只承諾 bounded-suboptimal，而不是 exact A* guarantee。

## 10. Exact Oracle 顯示 Heuristic Gap 還非常大

若直接把真正 exact distance-to-go 當 heuristic：

```text
expanded = 11
```

所以目前 Hybrid 的 132 距離理想還很遠。

這個 gap：

```text
132 -> 11
```

就是下一階段可以真正學習的空間。

## 11. 這輪最重要的三分法

現在必須明確分開：

### Prediction Quality

```text
模型猜 remaining cost 猜得多準？
```

### Admissibility

```text
h(K) 是否永遠不高估？
```

### Consistency

```text
h(K) <= c(K,K') + h(K')
```

三者不是同一件事。

一個 model 可以：

```text
很準但不 admissible；
admissible 但不 consistent；
consistent 但弱到幾乎沒用。
```

Round 22 第一次把這三層在 proof planner 裡實際分開。

## 12. Learned Heuristic 的安全架構

現在比較合理的 pipeline 是：

```text
kernel features
-> learned raw estimate
-> structural constraints (goal=0)
-> safety calibration
-> admissible envelope
-> A* / weighted A*
```

而不是：

```text
LLM / ML predicts cost
-> trust it
```

這和前面 certificate-carrying EMTS 的精神完全一致：

> 智能可以負責提出強估計，但安全層必須把它轉成可驗證的搜尋約束。

## 13. 自我改善 Planner 的第一個可行版本

現在可以有兩個通道：

```text
Safe channel:
  calibrated admissible heuristic
  -> exact A*

Fast channel:
  raw learned ranking
  -> candidate ordering / weighted / anytime search
```

然後每完成一次 exact search，又會得到新的：

```text
(kernel features, exact cost-to-go)
```

訓練資料。

所以 planner 可以形成：

```text
search
-> exact distances / successful paths
-> update heuristic model
-> recalibrate safety envelope
-> search again
```

這才是「self-improving proof planner」比較可信的版本。

## 14. Round 22 的限制

- model 只在同一 Round21 graph 上做 train/test；
- admissible calibration 使用了完整 graph exact labels，因此目前是 offline calibrated prototype；
- 沒有證明跨 horizon / 新 probe grammar 保持 calibration；
- structural burden weights 本身仍是研究用 audit weights。

所以還不能叫通用 learned theorem prover。

## 15. 下一輪

Round 23 最值得做：

```text
Cross-Graph Heuristic Transfer
```

把 heuristic 在一個 domain / grammar 上學到後，直接拿到：

- 不同 horizon；
- 不同 probe subset grammar；
- 不同 target-residual geometry；

測：

1. raw prediction 是否 transfer；
2. admissibility envelope 是否失效；
3. 如何只用少量新 exact searches 重新 calibration；
4. 能否形成真正 online adaptive heuristic。

這會區分：

```text
memorizing one kernel graph
```

和：

```text
learning reusable proof-search geometry.
```

## 16. Round 22 結論

```text
learned kernel geometry contains useful search signal;
raw predictive accuracy is not enough for safe A*;
admissibility and consistency are separate constraints;
graph-calibrated learned heuristics can reduce exact-search expansions;
weighted A* exposes an explicit guarantee-versus-speed axis;
the remaining gap to exact cost-to-go is still large.
```

---

```text
Round 22: COMPLETE
Next: Round 23 — Cross-Graph Heuristic Transfer
```