← Archive
lm-004252 · 2026-10

ESC-EXP-25:Minimal Provenance Coding for Recoverability

下載 MD 檔 ⬇
📎 附件 · Companion files — 隨文交付的程式 / 證明 / 資料,可獨立下載重驗

ESC-EXP-25:Minimal Provenance Coding for Recoverability

系列: Extensional Structural Convergence — Experimental Phase
文件編號: ESC-EXP-25
版本: v0.1
日期: 2026-09-23
前置: ESC-00 ~ ESC-06、ESC-EXP-00 ~ ESC-EXP-24
狀態: Information-Theoretic Provenance Coding Experiment

作者: Neo.K
機構: EveMissLab/一言諾科技有限公司


摘要

ESC-EXP-24 已經建立:

P0←MH←MC←O\boxed{ \mathcal P_0 \leftarrow M_H \leftarrow M_C \leftarrow O }

的 multi-tier recoverability architecture。

但 EXP-24 的 storage proxy 仍然非常粗:

∣MC∣−∣MH∣.|M_C|-|M_H|.

也就是:

Cold 比 Hot 多幾個 partition blocks,就把它當成多少 storage cost。

這個量可以用來做 finite structural optimization,但它不是資訊量。

本輪正式改成資訊論版本。

令:

SS

為 underlying atomic mechanism state,

H=h(S)H=h(S)

為 Hot class,

C=c(S)C=c(S)

為 finer Cold backing class,

且:

C⪯H.C\preceq H.

那麼在 Hot class 已知的前提下,要精確恢復 Cold class所需的最低 asymptotic average provenance rate為:

P(H→C)=H(C∣H).\boxed{ P(H\rightarrow C) = H(C\mid H). }

如果 Cold 已經是 atomic backing:

C=S,C=S,

則:

P(H→S)=H(S∣H).\boxed{ P(H\rightarrow S) = H(S\mid H). }

也就是:

Hot representation 已經知道之後,還差多少 bits 才能完全恢復 underlying atomic identity。

本輪得到幾個非常乾淨的結果。

Uniform Prior

目前 H4 active partition:

44

個 blocks,而且每個 block 都恰好包含:

22

個 equiprobable atomic states。

所以:

H(S∣H4)=1 bit/state.\boxed{ H(S\mid H4) = 1\text{ bit/state}. }

換句話說:

H4 表面上從 8 states 壓到 4 classes,但要保留 universal recoverability,Cold provenance其實只需要額外保存 1 bit/state。

Skewed Prior

同一個 H4 partition:

H(S∣H4)=0.811278124459 bits/state.\boxed{ H(S\mid H4) = 0.811278124459 \text{ bits/state}. }

所以 block-count:

+4+4

完全不能直接理解成「需要 4 個 units 的 information」。

真正 Shannon lower bound只有:

0.8112780.811278

bits/state。

更重要的是:

H4→H6:

+2 blocks+2\text{ blocks}

需要:

0.278661395441 bits/state,\boxed{ 0.278661395441 \text{ bits/state}, }

而 H6→H8:

同樣:

+2 blocks+2\text{ blocks}

卻需要:

0.532616729018 bits/state.\boxed{ 0.532616729018 \text{ bits/state}. }

所以:

same block increment≠same information increment.\boxed{ \text{same block increment} \neq \text{same information increment}. }

這正式推翻把:

∣MC∣−∣MH∣|M_C|-|M_H|

當成資訊量的解讀。


1. Runtime

EXP-25 regression:

7 passed

測試包含:

  • uniform H4→H8 精確需要 1 bit;
  • staged entropy coding滿足 chain rule;
  • uniform 的四種 H5 single-split 都是 0.25 bit;
  • skewed prior下四個 H5 split具有不同資訊價值;
  • conditional Huffman長度不低於 entropy lower bound且小於 H+1H+1 ;
  • atomic Cold backing residual uncertainty為 0;
  • H4 refinement menu共有:1616 個 partitions。

2. Provenance Code

假設存在 residual provenance code:

Z.Z.

而 Cold class可以由:

(H,Z)(H,Z)

精確重建:

C=f(H,Z).C = f(H,Z).

那麼:

H(C∣H,Z)=0.H(C\mid H,Z) = 0.

由資訊論基本不等式:

H(C∣H)≤H(Z∣H)≤H(Z).\boxed{ H(C\mid H) \le H(Z\mid H) \le H(Z). }

所以:

H(C∣H)\boxed{ H(C\mid H) }

是任何 exact provenance representation 的資訊下限。


3. Asymptotic Achievability

對 i.i.d. state sequence:

S1,…,Sn,S_1,\dots,S_n,

條件 source coding可以讓 average rate逼近:

H(C∣H).\boxed{ H(C\mid H). }

因此本輪把:

H(C∣H)H(C\mid H)

稱為:

Minimal Provenance Rate.\boxed{ \text{Minimal Provenance Rate}. }

這是 asymptotic average quantity。


4. One-Shot Prefix Coding 與 Shannon Limit 不同

若每個 state 都必須單獨使用 instantaneous binary prefix code,

實際 expected code length:

LprefixL_{\mathrm{prefix}}

一般滿足:

H(C∣H)≤Lprefix<H(C∣H)+1.\boxed{ H(C\mid H) \le L_{\mathrm{prefix}} < H(C\mid H)+1. }

所以:

  • Shannon entropy:理想長期 compression lower bound;
  • Huffman:one-shot prefix coding;
  • fixed-width tag:最簡單 runtime implementation。

三者不能混為同一個成本。


5. Canonical H4 Partition

目前 active / Hot H4:

{{∅,G},{D,DG},{T,TG},{TD,TDG}}.\boxed{ \{ \{\varnothing,G\}, \{D,DG\}, \{T,TG\}, \{TD,TDG\} \}. }

所以每個 Hot class仍保留一個 binary unresolved distinction。


6. Uniform H4 Entropy

Atomic state:

SS

uniform於 8 states。

所以:

H(S)=3 bits.H(S) = \boxed{ 3\text{ bits}. }

H4 有 4 equiprobable classes:

H(H4)=2 bits.H(H4) = \boxed{ 2\text{ bits}. }

因此:

H(S∣H4)=3−2=1 bit.\boxed{ H(S\mid H4) = 3-2 = 1\text{ bit}. }

7. H4→H8 Universal Cold

Cold:

H8=S.H8 = S.

所以:

P(H4→H8)=1 bit/state.\boxed{ P(H4\rightarrow H8) = 1\text{ bit/state}. }

而且每個 Hot block正好只有兩種 Cold child states。

因此:

LHuffman=1.\boxed{ L_{\mathrm{Huffman}} = 1. }

fixed-width tag也:

1 bit.\boxed{ 1\text{ bit}. }

這個 case 沒有 coding overhead。


8. EXP-24 Block Proxy vs 真實 Bits

EXP-24 會說:

H4→C8:+4 blocks.H4\rightarrow C8: \quad +4\text{ blocks}.

EXP-25 現在說:

+4 blocks⟶1 bit/state\boxed{ +4\text{ blocks} \longrightarrow 1\text{ bit/state} }

在 uniform prior 下。

所以:

block count\boxed{ \text{block count} }

只是結構複雜度 proxy,

不是 storage information。


9. Uniform H4→H6

Known-support H6:

{{∅,G},D,T,DG,{TD,TDG},TG}.\boxed{ \{ \{\varnothing,G\}, D, T, DG, \{TD,TDG\}, TG \}. }

它把 H4 的四個 binary ambiguities拆掉其中兩個。

所以:

H(H6)=2.5 bits.H(H6) = \boxed{ 2.5\text{ bits}. }

因此:

H(H6∣H4)=0.5 bit.\boxed{ H(H6\mid H4) = 0.5\text{ bit}. }

10. Uniform H6→H8

剩餘兩個 binary ambiguities:

{∅,G},\{\varnothing,G\}, {TD,TDG}.\{TD,TDG\}.

再拆開需要:

0.5 bit.\boxed{ 0.5\text{ bit}. }

所以:

0.5+0.5=1.\boxed{ 0.5+0.5=1. }

11. Provenance Chain Rule

對 nested partitions:

H←C←S,H \leftarrow C \leftarrow S,

有:

H(S)=H(H)+H(C∣H)+H(S∣C).\boxed{ H(S) = H(H) + H(C\mid H) + H(S\mid C). }

因此:

H(S∣H)=H(C∣H)+H(S∣C).\boxed{ H(S\mid H) = H(C\mid H) + H(S\mid C). }

這可以解讀成:

Hot 尚未解決的 atomic uncertainty,被分成「Cold 已保存的 provenance」與「Cold 之後仍未保存的 residue」。


12. Provenance Conservation Law

定義:

PC=H(C∣H)P_C = H(C\mid H)

為 stored provenance,

RC=H(S∣C)R_C = H(S\mid C)

為 residual atomic uncertainty。

則:

PC+RC=H(S∣H).\boxed{ P_C+R_C = H(S\mid H). }

在 ideal Shannon coding 下:

每多保存 1 bit provenance,就精確減少 1 bit unrecoverable residual uncertainty。


13. Uniform Provenance Ladder

H4:

P=0,R=1.P=0, \quad R=1.

H6:

P=0.5,R=0.5.P=0.5, \quad R=0.5.

H8:

P=1,R=0.P=1, \quad R=0.

所以:

(0,1)→(0.5,0.5)→(1,0).\boxed{ (0,1) \rightarrow (0.5,0.5) \rightarrow (1,0). }

這是 recoverability 的資訊論版直線 frontier。


14. Skewed Prior

本輪第二個 prior沿用 EXP-17 的 skewed 8-state distribution。

Atomic entropy:

H(S)=2.655447146846 bits.\boxed{ H(S) = 2.655447146846 \text{ bits}. }

H4 entropy:

H(H4)=1.844169022387 bits.\boxed{ H(H4) = 1.844169022387 \text{ bits}. }

所以:

H(S∣H4)=0.811278124459 bits.\boxed{ H(S\mid H4) = 0.811278124459 \text{ bits}. }

15. Skewed H4→H8

Shannon minimal provenance:

0.811278124459 bits/state.\boxed{ 0.811278124459 \text{ bits/state}. }

但是每個 Hot block仍然含兩個 possible atoms。

所以 one-shot binary prefix code仍至少要:

1 bit\boxed{ 1\text{ bit} }

每個 state。

因此:

LHuffman=1.\boxed{ L_{\mathrm{Huffman}} = 1. }

coding overhead:

1−0.811278124459=0.188721875541 bits/state.\boxed{ 1 - 0.811278124459 = 0.188721875541 \text{ bits/state}. }

16. Block Coding 的意義

這個:

0.1887220.188722

不是「不可避免的資訊」。

它是:

one-shot prefix constraint 相對 asymptotic Shannon coding 的 overhead。

如果允許長 block arithmetic / entropy coding,

average rate可以逼近:

0.811278.0.811278.

所以 multi-tier provenance runtime還要區分:

logical information requirement\boxed{ \text{logical information requirement} }

與:

coding-format overhead.\boxed{ \text{coding-format overhead}. }

17. Skewed H4→H6

同樣:

+2 blocks.+2\text{ blocks}.

但 minimal provenance只有:

0.278661395441 bits.\boxed{ 0.278661395441 \text{ bits}. }

Huffman:

0.343484419263.\boxed{ 0.343484419263. }

residual atomic uncertainty:

0.532616729018.\boxed{ 0.532616729018. }

18. Skewed H6→H8

也是:

+2 blocks.+2\text{ blocks}.

但資訊量:

0.532616729018 bits.\boxed{ 0.532616729018 \text{ bits}. }

Huffman:

0.656515580737.\boxed{ 0.656515580737. }

所以同樣:

+2+2

blocks,

後半段資訊量幾乎是前半段:

1.91×\boxed{ 1.91\times }

左右。


19. Staged Shannon Coding 不增加總 Bits

Skewed:

H(H6∣H4)=0.278661395441,H(H6\mid H4) = 0.278661395441, H(H8∣H6)=0.532616729018.H(H8\mid H6) = 0.532616729018.

相加:

0.811278124459.\boxed{ 0.811278124459. }

正好等於:

H(H8∣H4).H(H8\mid H4).

所以:

ideal provenance staging does not change total Shannon information.\boxed{ \text{ideal provenance staging does not change total Shannon information}. }

它只改變:

  • 哪些 bits 在哪一 tier;
  • 何時讀;
  • latency;
  • coding organization。

20. 本 Canonical Chain 的 Huffman 也沒有額外 Staging Penalty

本例:

L(H4→H6)=0.343484419263,L(H4\rightarrow H6) = 0.343484419263, L(H6→H8)=0.656515580737.L(H6\rightarrow H8) = 0.656515580737.

相加:

1.\boxed{ 1. }

direct H4→H8 Huffman:

1.\boxed{ 1. }

所以 canonical chain:

Huffman staging overhead=0.\boxed{ \text{Huffman staging overhead}=0. }

這不是一般 theorem。

只是本 finite pair-split geometry 的特殊結果。


21. H4 的四個 Binary Distinctions

H4 有四個 pair blocks:

B1={∅,G},B_1 = \{\varnothing,G\}, B2={D,DG},B_2 = \{D,DG\}, B3={T,TG},B_3 = \{T,TG\}, B4={TD,TDG}.B_4 = \{TD,TDG\}.

把其中任意一個 pair拆開:

4→54\rightarrow5

classes。


22. Uniform Prior:每個 Split 都是 0.250.25 Bit

因每個 H4 pair總 mass:

0.25,0.25,

conditional binary entropy:

1.1.

所以 contribution:

0.25×1=0.25 bit.0.25\times1 = \boxed{ 0.25\text{ bit}. }

四組完全相同。


23. Skewed Prior:同樣 +1 Class,資訊量完全不同

實測:

Split {T,TG}\{T,TG\}

0.110602718809 bits.\boxed{ 0.110602718809 \text{ bits}. }

Split {TD,TDG}\{TD,TDG\}

0.162887640428 bits.\boxed{ 0.162887640428 \text{ bits}. }

Split {D,DG}\{D,DG\}

0.168058676632 bits.\boxed{ 0.168058676632 \text{ bits}. }

Split {∅,G}\{\varnothing,G\}

0.369729088590 bits.\boxed{ 0.369729088590 \text{ bits}. }

全部都是:

4→5,4\rightarrow5,

但 information gain相差超過:

3.34×.\boxed{ 3.34\times. }

24. Block-Count Proxy 正式失效

所以:

Δ∣M∣=1\boxed{ \Delta|M| = 1 }

不能推出:

ΔI=constant.\boxed{ \Delta I = \text{constant}. }

甚至在完全相同 partition lattice depth 下,

資訊價值仍取決於:

  • prior;
  • block mass;
  • within-block uncertainty。

25. Immediate Split Value

對 Hot block:

BB

若把它拆成 child classes:

B1,…,Bm,B_1,\dots,B_m,

其 provenance information contribution:

V(B)=P(B)H(B1,…,Bm∣B).\boxed{ V(B) = P(B) H( B_1,\dots,B_m \mid B ). }

所以 split value不是「多一個 block」。

而是:

block probability×internal conditional entropy.\boxed{ \text{block probability} \times \text{internal conditional entropy}. }

26. Distinction Bit Value

因此可以把某個 latent distinction:

dd

的 recoverability storage value寫成:

I(d∣H)\boxed{ I(d\mid H) }

或在 pair-split case:

P(B)h2(p).\boxed{ P(B)h_2(p). }

這開始允許:

如果 Cold bit budget有限,優先保存哪些 distinctions?


27. Budgeted Provenance Selection

若 Cold provenance budget:

BcoldB_{\mathrm{cold}}

有限,

理想問題變成:

max⁡CH(C∣H)\boxed{ \max_C H(C\mid H) }

subject to:

CodeCost⁡(C∣H)≤Bcold.\boxed{ \operatorname{CodeCost}(C\mid H) \le B_{\mathrm{cold}}. }

等價地:

min⁡CH(S∣C).\boxed{ \min_C H(S\mid C). }

也就是在 storage budget內最小化 future unrecoverable residue。


28. H4 Refinement Menu

H4 有四個 binary pair blocks。

每一組可:

  • keep merged;
  • split。

所以 refinement menu共有:

24=16.\boxed{ 2^4 = 16. }

本輪完整枚舉全部 16 種。


29. Ideal Provenance Frontier

對任一 refinement:

C,C,

都有:

H(C∣H4)+H(S∣C)=H(S∣H4).\boxed{ H(C\mid H4) + H(S\mid C) = H(S\mid H4). }

所以 ideal entropy frontier是一條:

45∘\boxed{ 45^\circ }

資訊守恆線。

在 uniform:

P+R=1.P+R=1.

在 skewed:

P+R=0.811278124459.\boxed{ P+R = 0.811278124459. }

30. 為什麼還需要 Optimization?

如果 ideal bits與 residual完全一比一,

看起來似乎沒有 optimization。

但真實 runtime還有:

  • prefix-code overhead;
  • fixed-width overhead;
  • random-access constraint;
  • tier access cost;
  • block alignment;
  • update cost;
  • future target weighting;
  • nonuniform distinction value。

所以真正 planner不是只看 Shannon frontier。

而是:

information value÷physical code cost.\boxed{ \text{information value} \div \text{physical code cost}. }

31. Huffman Efficiency

定義:

ηcode=H(C∣H)Lprefix.\boxed{ \eta_{\mathrm{code}} = \frac{ H(C\mid H) }{ L_{\mathrm{prefix}} }. }

對 skewed H4→H8:

ηcode=0.811278.\eta_{\mathrm{code}} = 0.811278.

也就是 one-shot 1-bit residual tag有約:

81.13%81.13\%

的 Shannon efficiency。


32. Provenance Placement 與 EXP-24 的重新解讀

EXP-24:

H4−C8H4-C8

被視為 Cold多:

44

個 classes。

EXP-25 現在更精確地說:

Uniform

Cold residual:

1 bit/state.\boxed{ 1\text{ bit/state}. }

Skewed

ideal residual:

0.811278 bits/state.\boxed{ 0.811278\text{ bits/state}. }

所以 H4-C8 的 storage economics應該重新以:

ηC×H(S∣H4)\eta_C \times H(S\mid H4)

而不是:

ηC×4\eta_C \times4

建模。


33. EXP-24 的 Phase Boundaries 會因此重新縮放

例如 EXP-24:

H4−C8H4-C8

storage proxy:

4ηC.4\eta_C.

若改成 ideal uniform code:

1ηCbit.\boxed{ 1\eta_C^{\mathrm{bit}}. }

在 skewed prior甚至:

0.811278ηCbit.\boxed{ 0.811278 \eta_C^{\mathrm{bit}}. }

因此真正的 tier phase boundaries會依 physical bit cost重新移動。


34. Structural Cost 與 Information Cost 應分開保存

但這不代表 block count沒用。

Block count仍可能影響:

  • index complexity;
  • routing table size;
  • branching cost;
  • number of reconstruction cases;
  • metadata overhead。

所以應保存兩個軸:

Cstruct\boxed{ C_{\mathrm{struct}} }

與:

Cinfo.\boxed{ C_{\mathrm{info}}. }

其中:

Cstruct∼∣MC∣−∣MH∣,C_{\mathrm{struct}} \sim |M_C|-|M_H|, Cinfo=H(C∣H).C_{\mathrm{info}} = H(C\mid H).

35. Provenance Code 不只是 Raw Bit

Cold provenance可以實現為:

  • binary residual;
  • entropy-coded residual;
  • reversible transform index;
  • provenance DAG edge;
  • reconstruction seed;
  • delta code;
  • external pointer。

只要:

(H,Z)↦C(H,Z) \mapsto C

可恢復,

它都是合法 provenance code。


36. Provenance Lower Bound 適用所有實現

不論 physical encoding為何,

只要 exact recovery:

H(C∣H,Z)=0,H(C\mid H,Z)=0,

就有:

H(Z∣H)≥H(C∣H).\boxed{ H(Z\mid H) \ge H(C\mid H). }

所以:

H(C∣H)\boxed{ H(C\mid H) }

是跨 physical representation 的共同理論下限。


37. Cold Provenance 不一定要重複 Hot 資訊

如果 Hot class:

HH

已知,

Cold只需要保存 residual:

Z.Z.

不需要重新存:

H.H.

所以正確 storage decomposition是:

Hot+Conditional Residual.\boxed{ \text{Hot} + \text{Conditional Residual}. }

而不是:

Hot+Full Raw State Copy.\boxed{ \text{Hot} + \text{Full Raw State Copy}. }

38. Recoverability Coding Gain

若 raw atomic state entropy:

H(S),H(S),

Hot已保留:

H(H),H(H),

那 Cold provenance只需要:

H(S)−H(H).\boxed{ H(S)-H(H). }

所以 relative to full duplicate storage,節省:

H(H).\boxed{ H(H). }

這就是 Hot side information 的 coding gain。


39. Uniform Example

Raw:

H(S)=3.H(S)=3.

Hot:

H(H4)=2.H(H4)=2.

Cold residual:

1.1.

所以完整 recoverability architecture可以是:

2 hot bits+1 cold residual bit.\boxed{ 2\text{ hot bits} + 1\text{ cold residual bit}. }

而不是:

2+3=52 + 3 = 5

bits 的 full duplication。


40. Skewed Example

Raw entropy:

2.655447.2.655447.

Hot entropy:

1.844169.1.844169.

Cold ideal residual:

0.811278.0.811278.

同樣:

1.844169+0.811278=2.655447.\boxed{ 1.844169 + 0.811278 = 2.655447. }

沒有資訊重複。


41. Multi-Tier Chain Rule

更一般:

M0⪰M1⪰⋯⪰Mk=S.M_0 \succeq M_1 \succeq \dots \succeq M_k = S.

則:

H(S)=H(M0)+∑i=1kH(Mi∣Mi−1).\boxed{ H(S) = H(M_0) + \sum_{i=1}^{k} H( M_i \mid M_{i-1} ). }

所以任意多層 recoverability hierarchy都可以用 conditional residual layers來實現。


42. Tiering 不增加理想總資訊

理想 Shannon world:

∑iH(Mi∣Mi−1)=H(S∣M0).\boxed{ \sum_i H( M_i \mid M_{i-1} ) = H(S\mid M_0). }

所以把 residual分:

  • Hot residual;
  • Warm residual;
  • Cold residual;

不會憑空增加必要資訊。

增加的是 physical implementation overhead。


43. Provenance Temperature 2.0

EXP-24 的 distinction temperature:

T(d)∈{H,C,O}T(d) \in \{H,C,O\}

現在可以再細化成:

每個 residual bit 的 storage temperature.\boxed{ \text{每個 residual bit 的 storage temperature}. }

不是整個 partition一起移動。

這讓 tier planner從:

partition placement\text{partition placement}

進一步變成:

information-bit placement.\boxed{ \text{information-bit placement}. }

44. Distinction-Level Cold Allocation

skewed prior中,如果 Cold只能先保存一個 H4 pair split,

理想 recoverability gain排序是:

{∅,G}>{D,DG}>{TD,TDG}>{T,TG}\boxed{ \{\varnothing,G\} > \{D,DG\} > \{TD,TDG\} > \{T,TG\} }

依 provenance bits約:

0.369729,0.369729, 0.168059,0.168059, 0.162888,0.162888, 0.110603.0.110603.

所以「先保存哪一個 distinction」現在可以定量。


45. 但資訊量不是唯一 Priority

如果某個 low-probability distinction:

  • future failure cost極高;
  • irrecoverable;
  • safety critical;

即使:

H(d)H(d)

小,也可能優先 Cold-store。

所以最終 ranking需要:

information×future value/risk.\boxed{ \text{information} \times \text{future value/risk}. }

EXP-25只建立 information axis。


46. Recoverability Rate

可以正式定義:

Rprov(C∣H)=H(C∣H).\boxed{ R_{\mathrm{prov}} ( C\mid H ) = H(C\mid H). }

若要求 atomic recovery:

Ratomic(H)=H(S∣H).\boxed{ R_{\mathrm{atomic}} (H) = H(S\mid H). }

這是 representation 的:

recoverability rate.\boxed{ \text{recoverability rate}. }

47. Recoverability Efficiency

如果 physical Cold code平均長度:

LC,L_C,

定義:

ηR=H(C∣H)LC.\boxed{ \eta_R = \frac{ H(C\mid H) }{ L_C }. } 0<ηR≤1.0<\eta_R\le1.

越接近:

11

越接近理論最小 provenance code。


48. 完整 Cost Vector

到這一步,Cold backing成本至少應寫成:

CC=(Cstruct,Cinfo,Ccode,Clatency,Cupdate).\boxed{ \mathbf C_C = ( C_{\mathrm{struct}}, C_{\mathrm{info}}, C_{\mathrm{code}}, C_{\mathrm{latency}}, C_{\mathrm{update}} ). }

所以單一:

∣MC∣|M_C|

已經明顯不夠。


49. 回接 EXP-06 Bridge Cost

EXP-06 定義 bridge cost:

Cbridge=min⁡H(SP).\mathcal C_{\mathrm{bridge}} = \min H(S_P).

EXP-25 現在其實形成一個非常直接的 recoverability版本:

Cprov(H→C)=H(C∣H).\boxed{ \mathcal C_{\mathrm{prov}} (H\rightarrow C) = H(C\mid H). }

所以:

bridge\boxed{ \text{bridge} }

與:

provenance residual\boxed{ \text{provenance residual} }

其實是同一個 conditional-information問題的兩種方向。


50. 回接 EXP-12 Epistemic Uncertainty

EXP-12 使用:

H(J∣Π)H(J\mid\Pi)

表示 target-specific residual uncertainty。

EXP-25 使用:

H(S∣H)H(S\mid H)

表示 atomic identity residual uncertainty。

因此:

recoverability code length\boxed{ \text{recoverability code length} }

正好等於:

要消除的 residual uncertainty\boxed{ \text{要消除的 residual uncertainty} }

在 ideal coding下。


51. 回接 ESC 最早的 Complete Recoverability

CER原本問:

observation 是否足以唯一恢復 underlying identity?

EXP-25現在把這件事量化。

如果 Hot不滿足 CER:

H(S∣H)>0.H(S\mid H)>0.

那麼使 system重新具備 complete recovery所需的最低 side information rate就是:

H(S∣H).\boxed{ H(S\mid H). }

所以:

CER failure\boxed{ \text{CER failure} }

不再只是 yes/no。

還有:

distance-to-CER in bits.\boxed{ \text{distance-to-CER in bits}. }

52. Information-Theoretic Recoverability Gap

因此定義:

GR(H)=H(S∣H).\boxed{ G_R(H) = H(S\mid H). }

如果:

GR=0,G_R=0,

Hot自身已 complete recoverable。

如果:

GR>0,G_R>0,

就是 exact recovery仍缺多少 ideal bits。

本輪:

Uniform H4

GR=1.\boxed{ G_R=1. }

Skewed H4

GR=0.811278.\boxed{ G_R=0.811278. }

53. Structural Gap 與 Information Gap

EXP-23 structural support gap:

8−6=2.8-6=2.

EXP-25則給 information gap。

兩者不同:

Gstruct\boxed{ G_{\mathrm{struct}} }

描述少幾個 partition distinctions,

Ginfo\boxed{ G_{\mathrm{info}} }

描述少幾 bits。

所以未來 ESC應同時報:

(Gstruct,Ginfo).\boxed{ ( G_{\mathrm{struct}}, G_{\mathrm{info}} ). }

54. 本輪錨點

ESC-EXP-25.ACprov(H→C)=H(C∣H).\boxed{ \textbf{ESC-EXP-25.A} \quad \mathcal C_{\mathrm{prov}} (H\rightarrow C) = H(C\mid H). } ESC-EXP-25.BH(S∣H)=H(C∣H)+H(S∣C).\boxed{ \textbf{ESC-EXP-25.B} \quad H(S\mid H) = H(C\mid H) + H(S\mid C). } ESC-EXP-25.Cuniform H4→H8 universal recoverability只需要 1 bit/state。\boxed{ \textbf{ESC-EXP-25.C} \quad \text{uniform H4→H8 universal recoverability只需要 1 bit/state。} } ESC-EXP-25.Dskewed H4→H8 Shannon minimum為 0.811278124459 bits/state。\boxed{ \textbf{ESC-EXP-25.D} \quad \text{skewed H4→H8 Shannon minimum為 }0.811278124459\text{ bits/state。} } ESC-EXP-25.Esame class-count increment can differ substantially in provenance information value。\boxed{ \textbf{ESC-EXP-25.E} \quad \text{same class-count increment can differ substantially in provenance information value。} }

55. 從 EXP-24 到 EXP-25 的真正修正

EXP-24:

Where should distinctions be stored?\boxed{ \text{Where should distinctions be stored?} }

EXP-25:

How many actual bits must each tier store?\boxed{ \text{How many actual bits must each tier store?} }

所以 multi-tier recoverability現在開始從 partition architecture進入:

coded recoverability architecture.\boxed{ \text{coded recoverability architecture}. }

56. 下一輪:ESC-EXP-26

EXP-25 假設 provenance code只需要支援:

exact reconstruction.\boxed{ \text{exact reconstruction}. }

但真實系統還有另一個巨大問題:

Cold code不只要小,還要能 random access、局部更新、局部解碼,而且未必每次都需要完整 H8 recovery。

所以下一輪最自然的是:

Task-Adaptive Provenance Coding / Selective Recoverability.\boxed{ \text{Task-Adaptive Provenance Coding / Selective Recoverability}. }

也就是不再永遠要求:

SS

完整重建,

而是 future task:

JJ

來了之後,只解碼足以恢復:

J(S)J(S)

的 provenance bits。

可以研究:

  • task-conditioned code:H(J∣H);H(J\mid H);
  • universal provenance code vs selective code;
  • progressive / layered residual coding;
  • random-access provenance;
  • which residual bits unlock which future distinctions;
  • multi-task rate region。

真正問題會變成:

Cold provenance要不要一次存成 universal residual,還是做成可以按 future task逐層解鎖的 progressive code?

這會把 multi-tier recoverability從「storage hierarchy」再推進到:

semantic progressive coding.\boxed{ \text{semantic progressive coding}. }