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 幾乎沒有幫助：

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

所以 Round 22 問：

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

2. Learned Features

本輪 regression 使用：

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：

RMSE = 0.764
MAE  = 0.428

但 raw predictor 在 test nodes 上約：

37.65%

會高估 exact remaining cost。

所以：

predictive accuracy != admissibility

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

4. Goal-Zero + Calibration

我們先強制：

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

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

h(goal)=0

接著再做 safety calibration。

Global scaling

單一 global scale：

alpha = 0.042817

非常保守。

Piecewise calibration

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

這是：

graph-calibrated admissible heuristic

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

5. Hybrid Heuristic

最後：

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

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

本輪全節點驗證：

admissible = True

6. Consistency 是第三件不同的事

Hybrid heuristic 雖 admissible，但：

consistent = False
max consistency violation = 1.672

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

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

實際這張 graph 上：

reexpanded events = 0

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

7. Search 結果

最重要的三個數字：

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

因此：

safe learned/adaptive heuristic

已把 expansion 降約：

10.81%

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

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

Raw model 本輪碰巧仍找到 optimum：

cost = 7.8

且只展開 63 nodes。

但這只是 observed outcome。

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

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：

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

最激進的 w=3：

expanded = 91

相對 UCS 減少：

38.51%

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

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

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

expanded = 11

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

這個 gap：

132 -> 11

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

11. 這輪最重要的三分法

現在必須明確分開：

Prediction Quality

模型猜 remaining cost 猜得多準？

Admissibility

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

Consistency

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

三者不是同一件事。

一個 model 可以：

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

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

12. Learned Heuristic 的安全架構

現在比較合理的 pipeline 是：

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

而不是：

LLM / ML predicts cost
-> trust it

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

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

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

現在可以有兩個通道：

Safe channel:
  calibrated admissible heuristic
  -> exact A*

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

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

(kernel features, exact cost-to-go)

訓練資料。

所以 planner 可以形成：

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 最值得做：

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。

這會區分：

memorizing one kernel graph

和：

learning reusable proof-search geometry.

16. Round 22 結論

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.

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