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
的 multi-tier recoverability architecture。
但 EXP-24 的 storage proxy 仍然非常粗:
∣MC∣−∣MH∣.
也就是:
Cold 比 Hot 多幾個 partition blocks,就把它當成多少 storage cost。
這個量可以用來做 finite structural optimization,但它不是資訊量。
本輪正式改成資訊論版本。
令:
S
為 underlying atomic mechanism state,
H=h(S)
為 Hot class,
C=c(S)
為 finer Cold backing class,
且:
C⪯H.
那麼在 Hot class 已知的前提下,要精確恢復 Cold class所需的最低 asymptotic average provenance rate為:
P(H→C)=H(C∣H).
如果 Cold 已經是 atomic backing:
C=S,
則:
P(H→S)=H(S∣H).
也就是:
Hot representation 已經知道之後,還差多少 bits 才能完全恢復 underlying atomic identity。
本輪得到幾個非常乾淨的結果。
Uniform Prior
目前 H4 active partition:
4
個 blocks,而且每個 block 都恰好包含:
2
個 equiprobable atomic states。
所以:
H(S∣H4)=1 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.
所以 block-count:
+4
完全不能直接理解成「需要 4 個 units 的 information」。
真正 Shannon lower bound只有:
0.811278
bits/state。
更重要的是:
H4→H6:
+2 blocks
需要:
0.278661395441 bits/state,
而 H6→H8:
同樣:
+2 blocks
卻需要:
0.532616729018 bits/state.
所以:
same block increment=same information increment.
這正式推翻把:
∣MC∣−∣MH∣
當成資訊量的解讀。
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+1 ;
- atomic Cold backing residual uncertainty為 0;
- H4 refinement menu共有:16
個 partitions。
2. Provenance Code
假設存在 residual provenance code:
Z.
而 Cold class可以由:
(H,Z)
精確重建:
C=f(H,Z).
那麼:
H(C∣H,Z)=0.
由資訊論基本不等式:
H(C∣H)≤H(Z∣H)≤H(Z).
所以:
H(C∣H)
是任何 exact provenance representation 的資訊下限。
3. Asymptotic Achievability
對 i.i.d. state sequence:
S1,…,Sn,
條件 source coding可以讓 average rate逼近:
H(C∣H).
因此本輪把:
H(C∣H)
稱為:
Minimal Provenance Rate.
這是 asymptotic average quantity。
4. One-Shot Prefix Coding 與 Shannon Limit 不同
若每個 state 都必須單獨使用 instantaneous binary prefix code,
實際 expected code length:
Lprefix
一般滿足:
H(C∣H)≤Lprefix<H(C∣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}}.
所以每個 Hot class仍保留一個 binary unresolved distinction。
6. Uniform H4 Entropy
Atomic state:
S
uniform於 8 states。
所以:
H(S)=3 bits.
H4 有 4 equiprobable classes:
H(H4)=2 bits.
因此:
H(S∣H4)=3−2=1 bit.
7. H4→H8 Universal Cold
Cold:
H8=S.
所以:
P(H4→H8)=1 bit/state.
而且每個 Hot block正好只有兩種 Cold child states。
因此:
LHuffman=1.
fixed-width tag也:
1 bit.
這個 case 沒有 coding overhead。
8. EXP-24 Block Proxy vs 真實 Bits
EXP-24 會說:
H4→C8:+4 blocks.
EXP-25 現在說:
+4 blocks⟶1 bit/state
在 uniform prior 下。
所以:
block count
只是結構複雜度 proxy,
不是 storage information。
9. Uniform H4→H6
Known-support H6:
{{∅,G},D,T,DG,{TD,TDG},TG}.
它把 H4 的四個 binary ambiguities拆掉其中兩個。
所以:
H(H6)=2.5 bits.
因此:
H(H6∣H4)=0.5 bit.
10. Uniform H6→H8
剩餘兩個 binary ambiguities:
{∅,G},
{TD,TDG}.
再拆開需要:
0.5 bit.
所以:
0.5+0.5=1.
11. Provenance Chain Rule
對 nested partitions:
H←C←S,
有:
H(S)=H(H)+H(C∣H)+H(S∣C).
因此:
H(S∣H)=H(C∣H)+H(S∣C).
這可以解讀成:
Hot 尚未解決的 atomic uncertainty,被分成「Cold 已保存的 provenance」與「Cold 之後仍未保存的 residue」。
12. Provenance Conservation Law
定義:
PC=H(C∣H)
為 stored provenance,
RC=H(S∣C)
為 residual atomic uncertainty。
則:
PC+RC=H(S∣H).
在 ideal Shannon coding 下:
每多保存 1 bit provenance,就精確減少 1 bit unrecoverable residual uncertainty。
13. Uniform Provenance Ladder
H4:
P=0,R=1.
H6:
P=0.5,R=0.5.
H8:
P=1,R=0.
所以:
(0,1)→(0.5,0.5)→(1,0).
這是 recoverability 的資訊論版直線 frontier。
14. Skewed Prior
本輪第二個 prior沿用 EXP-17 的 skewed 8-state distribution。
Atomic entropy:
H(S)=2.655447146846 bits.
H4 entropy:
H(H4)=1.844169022387 bits.
所以:
H(S∣H4)=0.811278124459 bits.
15. Skewed H4→H8
Shannon minimal provenance:
0.811278124459 bits/state.
但是每個 Hot block仍然含兩個 possible atoms。
所以 one-shot binary prefix code仍至少要:
1 bit
每個 state。
因此:
LHuffman=1.
coding overhead:
1−0.811278124459=0.188721875541 bits/state.
16. Block Coding 的意義
這個:
0.188722
不是「不可避免的資訊」。
它是:
one-shot prefix constraint 相對 asymptotic Shannon coding 的 overhead。
如果允許長 block arithmetic / entropy coding,
average rate可以逼近:
0.811278.
所以 multi-tier provenance runtime還要區分:
logical information requirement
與:
coding-format overhead.
17. Skewed H4→H6
同樣:
+2 blocks.
但 minimal provenance只有:
0.278661395441 bits.
Huffman:
0.343484419263.
residual atomic uncertainty:
0.532616729018.
18. Skewed H6→H8
也是:
+2 blocks.
但資訊量:
0.532616729018 bits.
Huffman:
0.656515580737.
所以同樣:
+2
blocks,
後半段資訊量幾乎是前半段:
1.91×
左右。
19. Staged Shannon Coding 不增加總 Bits
Skewed:
H(H6∣H4)=0.278661395441,
H(H8∣H6)=0.532616729018.
相加:
0.811278124459.
正好等於:
H(H8∣H4).
所以:
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(H6→H8)=0.656515580737.
相加:
1.
direct H4→H8 Huffman:
1.
所以 canonical chain:
Huffman staging overhead=0.
這不是一般 theorem。
只是本 finite pair-split geometry 的特殊結果。
21. H4 的四個 Binary Distinctions
H4 有四個 pair blocks:
B1={∅,G},
B2={D,DG},
B3={T,TG},
B4={TD,TDG}.
把其中任意一個 pair拆開:
4→5
classes。
22. Uniform Prior:每個 Split 都是 0.25 Bit
因每個 H4 pair總 mass:
0.25,
conditional binary entropy:
1.
所以 contribution:
0.25×1=0.25 bit.
四組完全相同。
23. Skewed Prior:同樣 +1 Class,資訊量完全不同
實測:
Split {T,TG}
0.110602718809 bits.
Split {TD,TDG}
0.162887640428 bits.
Split {D,DG}
0.168058676632 bits.
Split {∅,G}
0.369729088590 bits.
全部都是:
4→5,
但 information gain相差超過:
3.34×.
24. Block-Count Proxy 正式失效
所以:
Δ∣M∣=1
不能推出:
ΔI=constant.
甚至在完全相同 partition lattice depth 下,
資訊價值仍取決於:
- prior;
- block mass;
- within-block uncertainty。
25. Immediate Split Value
對 Hot block:
B
若把它拆成 child classes:
B1,…,Bm,
其 provenance information contribution:
V(B)=P(B)H(B1,…,Bm∣B).
所以 split value不是「多一個 block」。
而是:
block probability×internal conditional entropy.
26. Distinction Bit Value
因此可以把某個 latent distinction:
d
的 recoverability storage value寫成:
I(d∣H)
或在 pair-split case:
P(B)h2(p).
這開始允許:
如果 Cold bit budget有限,優先保存哪些 distinctions?
27. Budgeted Provenance Selection
若 Cold provenance budget:
Bcold
有限,
理想問題變成:
CmaxH(C∣H)
subject to:
CodeCost(C∣H)≤Bcold.
等價地:
CminH(S∣C).
也就是在 storage budget內最小化 future unrecoverable residue。
28. H4 Refinement Menu
H4 有四個 binary pair blocks。
每一組可:
所以 refinement menu共有:
24=16.
本輪完整枚舉全部 16 種。
29. Ideal Provenance Frontier
對任一 refinement:
C,
都有:
H(C∣H4)+H(S∣C)=H(S∣H4).
所以 ideal entropy frontier是一條:
45∘
資訊守恆線。
在 uniform:
P+R=1.
在 skewed:
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.
31. Huffman Efficiency
定義:
ηcode=LprefixH(C∣H).
對 skewed H4→H8:
ηcode=0.811278.
也就是 one-shot 1-bit residual tag有約:
81.13%
的 Shannon efficiency。
32. Provenance Placement 與 EXP-24 的重新解讀
EXP-24:
H4−C8
被視為 Cold多:
4
個 classes。
EXP-25 現在更精確地說:
Uniform
Cold residual:
1 bit/state.
Skewed
ideal residual:
0.811278 bits/state.
所以 H4-C8 的 storage economics應該重新以:
ηC×H(S∣H4)
而不是:
ηC×4
建模。
33. EXP-24 的 Phase Boundaries 會因此重新縮放
例如 EXP-24:
H4−C8
storage proxy:
4ηC.
若改成 ideal uniform code:
1ηCbit.
在 skewed prior甚至:
0.811278ηCbit.
因此真正的 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
與:
Cinfo.
其中:
Cstruct∼∣MC∣−∣MH∣,
Cinfo=H(C∣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
可恢復,
它都是合法 provenance code。
36. Provenance Lower Bound 適用所有實現
不論 physical encoding為何,
只要 exact recovery:
H(C∣H,Z)=0,
就有:
H(Z∣H)≥H(C∣H).
所以:
H(C∣H)
是跨 physical representation 的共同理論下限。
37. Cold Provenance 不一定要重複 Hot 資訊
如果 Hot class:
H
已知,
Cold只需要保存 residual:
Z.
不需要重新存:
H.
所以正確 storage decomposition是:
Hot+Conditional Residual.
而不是:
Hot+Full Raw State Copy.
38. Recoverability Coding Gain
若 raw atomic state entropy:
H(S),
Hot已保留:
H(H),
那 Cold provenance只需要:
H(S)−H(H).
所以 relative to full duplicate storage,節省:
H(H).
這就是 Hot side information 的 coding gain。
39. Uniform Example
Raw:
H(S)=3.
Hot:
H(H4)=2.
Cold residual:
1.
所以完整 recoverability architecture可以是:
2 hot bits+1 cold residual bit.
而不是:
2+3=5
bits 的 full duplication。
40. Skewed Example
Raw entropy:
2.655447.
Hot entropy:
1.844169.
Cold ideal residual:
0.811278.
同樣:
1.844169+0.811278=2.655447.
沒有資訊重複。
41. Multi-Tier Chain Rule
更一般:
M0⪰M1⪰⋯⪰Mk=S.
則:
H(S)=H(M0)+i=1∑kH(Mi∣Mi−1).
所以任意多層 recoverability hierarchy都可以用 conditional residual layers來實現。
42. Tiering 不增加理想總資訊
理想 Shannon world:
i∑H(Mi∣Mi−1)=H(S∣M0).
所以把 residual分:
- Hot residual;
- Warm residual;
- Cold residual;
不會憑空增加必要資訊。
增加的是 physical implementation overhead。
43. Provenance Temperature 2.0
EXP-24 的 distinction temperature:
T(d)∈{H,C,O}
現在可以再細化成:
每個 residual bit 的 storage temperature.
不是整個 partition一起移動。
這讓 tier planner從:
partition placement
進一步變成:
information-bit placement.
44. Distinction-Level Cold Allocation
skewed prior中,如果 Cold只能先保存一個 H4 pair split,
理想 recoverability gain排序是:
{∅,G}>{D,DG}>{TD,TDG}>{T,TG}
依 provenance bits約:
0.369729,
0.168059,
0.162888,
0.110603.
所以「先保存哪一個 distinction」現在可以定量。
45. 但資訊量不是唯一 Priority
如果某個 low-probability distinction:
- future failure cost極高;
- irrecoverable;
- safety critical;
即使:
H(d)
小,也可能優先 Cold-store。
所以最終 ranking需要:
information×future value/risk.
EXP-25只建立 information axis。
46. Recoverability Rate
可以正式定義:
Rprov(C∣H)=H(C∣H).
若要求 atomic recovery:
Ratomic(H)=H(S∣H).
這是 representation 的:
recoverability rate.
47. Recoverability Efficiency
如果 physical Cold code平均長度:
LC,
定義:
ηR=LCH(C∣H).
0<ηR≤1.
越接近:
1
越接近理論最小 provenance code。
48. 完整 Cost Vector
到這一步,Cold backing成本至少應寫成:
CC=(Cstruct,Cinfo,Ccode,Clatency,Cupdate).
所以單一:
∣MC∣
已經明顯不夠。
49. 回接 EXP-06 Bridge Cost
EXP-06 定義 bridge cost:
Cbridge=minH(SP).
EXP-25 現在其實形成一個非常直接的 recoverability版本:
Cprov(H→C)=H(C∣H).
所以:
bridge
與:
provenance residual
其實是同一個 conditional-information問題的兩種方向。
50. 回接 EXP-12 Epistemic Uncertainty
EXP-12 使用:
H(J∣Π)
表示 target-specific residual uncertainty。
EXP-25 使用:
H(S∣H)
表示 atomic identity residual uncertainty。
因此:
recoverability code length
正好等於:
要消除的 residual uncertainty
在 ideal coding下。
51. 回接 ESC 最早的 Complete Recoverability
CER原本問:
observation 是否足以唯一恢復 underlying identity?
EXP-25現在把這件事量化。
如果 Hot不滿足 CER:
H(S∣H)>0.
那麼使 system重新具備 complete recovery所需的最低 side information rate就是:
H(S∣H).
所以:
CER failure
不再只是 yes/no。
還有:
distance-to-CER in bits.
52. Information-Theoretic Recoverability Gap
因此定義:
GR(H)=H(S∣H).
如果:
GR=0,
Hot自身已 complete recoverable。
如果:
GR>0,
就是 exact recovery仍缺多少 ideal bits。
本輪:
Uniform H4
GR=1.
Skewed H4
GR=0.811278.
53. Structural Gap 與 Information Gap
EXP-23 structural support gap:
8−6=2.
EXP-25則給 information gap。
兩者不同:
Gstruct
描述少幾個 partition distinctions,
Ginfo
描述少幾 bits。
所以未來 ESC應同時報:
(Gstruct,Ginfo).
54. 本輪錨點
ESC-EXP-25.ACprov(H→C)=H(C∣H).
ESC-EXP-25.BH(S∣H)=H(C∣H)+H(S∣C).
ESC-EXP-25.Cuniform H4→H8 universal recoverability只需要 1 bit/state。
ESC-EXP-25.Dskewed H4→H8 Shannon minimum為 0.811278124459 bits/state。
ESC-EXP-25.Esame class-count increment can differ substantially in provenance information value。
55. 從 EXP-24 到 EXP-25 的真正修正
EXP-24:
Where should distinctions be stored?
EXP-25:
How many actual bits must each tier store?
所以 multi-tier recoverability現在開始從 partition architecture進入:
coded recoverability architecture.
56. 下一輪:ESC-EXP-26
EXP-25 假設 provenance code只需要支援:
exact reconstruction.
但真實系統還有另一個巨大問題:
Cold code不只要小,還要能 random access、局部更新、局部解碼,而且未必每次都需要完整 H8 recovery。
所以下一輪最自然的是:
Task-Adaptive Provenance Coding / Selective Recoverability.
也就是不再永遠要求:
S
完整重建,
而是 future task:
J
來了之後,只解碼足以恢復:
J(S)
的 provenance bits。
可以研究:
- task-conditioned code:H(J∣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.