Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.19137 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908847255322624 |
|---|---|
| author | Xu, Jianfeng |
| author_facet | Xu, Jianfeng |
| contents | We introduce derivation depth-a computable metric of the reasoning effort needed to answer a query based on a given set of premises. We model information as a two-layered structure linking abstract knowledge with physical carriers, and separate essential core facts from operational shortcuts. For any finite premise base, we define and prove the computability of derivation depth. By encoding reasoning traces and applying information-theoretic incompressibility arguments, we establish fundamental bounds linking depth to the descriptive complexity of queries. For frequently asked, information-rich queries, the minimal description length grows proportionally to depth times the logarithm of the knowledge base size. This leads to a practical storage-computation tradeoff: queries accessed beyond a critical threshold become cheaper to cache than recompute. We formulate optimal cache allocation as a mathematical optimization problem solvable with approximation guarantees and extend the framework to handle noisy or incomplete knowledge bases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_19137 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Derivation Depth as an Information Metric: Axioms, Coding Theorems, and Storage--Computation Tradeoffs Xu, Jianfeng Information Theory We introduce derivation depth-a computable metric of the reasoning effort needed to answer a query based on a given set of premises. We model information as a two-layered structure linking abstract knowledge with physical carriers, and separate essential core facts from operational shortcuts. For any finite premise base, we define and prove the computability of derivation depth. By encoding reasoning traces and applying information-theoretic incompressibility arguments, we establish fundamental bounds linking depth to the descriptive complexity of queries. For frequently asked, information-rich queries, the minimal description length grows proportionally to depth times the logarithm of the knowledge base size. This leads to a practical storage-computation tradeoff: queries accessed beyond a critical threshold become cheaper to cache than recompute. We formulate optimal cache allocation as a mathematical optimization problem solvable with approximation guarantees and extend the framework to handle noisy or incomplete knowledge bases. |
| title | Derivation Depth as an Information Metric: Axioms, Coding Theorems, and Storage--Computation Tradeoffs |
| topic | Information Theory |
| url | https://arxiv.org/abs/2602.19137 |