🔢 mathematics

Derivation Depth as an Information Metric: Axioms, Coding Theorems, and Storage--Computation Tradeoffs

This paper introduces derivation depth as a computable metric for reasoning effort, establishing theoretical bounds that link query complexity to knowledge base size and revealing a fundamental storage-computation tradeoff where frequently accessed queries become more efficient to cache than to recompute.

Original authors: Jianfeng Xu

Published 2026-02-24

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jianfeng Xu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Library vs. Brain" Dilemma

Imagine you are running a massive, super-smart library (a Knowledge Base). People come in asking complex questions (Queries). You have two ways to answer them:

The "Brain" Approach (Derivation): You keep the library shelves clean and minimal. When someone asks a question, you use your brain to read the books, connect the dots, and figure out the answer from scratch. This is fast on storage (you don't need many books) but slow on time (you have to think hard).
The "Cheat Sheet" Approach (Caching): You write down the answers to the most popular questions on sticky notes and stick them on the front door. When someone asks, you just hand them the note. This is instant (fast computation) but takes up wall space (storage cost).

The Problem: You have a limited budget. You can't write down every answer (too much wall space), but you can't afford to think about every question from scratch (too much time).

The Paper's Solution: The author, Jianfeng Xu, proposes a new way to measure exactly how hard it is to think about a question. He calls this "Derivation Depth." Using this measurement, he creates a mathematical rule to tell you exactly which answers to write down and which to figure out on the fly to save the most money and time.

Key Concepts Explained with Analogies

1. The "Core" vs. The "Shortcuts"

Imagine your library has a Core Collection (the essential, non-redundant facts) and a Shortcut Collection (pre-written summaries).

The Core: If you remove a book from the Core, you can't reconstruct the story anymore. It's the "atomic truth."
The Shortcuts: These are helpful summaries. If you lose a summary, you can still find the answer by reading the Core books, but it takes longer.
The Insight: The paper separates these two. It says, "Let's measure the difficulty of an answer based only on the Core. If we have shortcuts, the difficulty drops. We need to know exactly how much difficulty we are saving."

2. Derivation Depth (The "Ladder" Analogy)

Think of answering a question like climbing a ladder.

Depth 0: The answer is already in your pocket (you have the shortcut). You don't need to climb.
Depth 1: You need to look at one book to find the answer. One step up the ladder.
Depth 10: You need to read 10 books, connecting them in a specific chain. Ten steps up the ladder.

Derivation Depth is simply counting how many rungs you have to climb to get the answer. The paper proves that the number of rungs you climb is directly related to how much "information" is in the question. If a question is very complex (high information), you usually have to climb a tall ladder.

3. The "Break-Even" Point (The Coffee Shop Analogy)

Imagine you run a coffee shop.

Making coffee from scratch (Derivation): Costs you 5 minutes of your time per cup.
Buying pre-made coffee (Caching): Costs you $2 to buy the machine and keep it stocked.

If you only sell 1 cup a day, it's cheaper to make it from scratch.
If you sell 1,000 cups a day, it's cheaper to buy the machine.

The paper calculates a specific "Break-Even Frequency." It tells you: "If you expect to be asked this specific question more than X times, write it down. If less, figure it out."

The Twist: The "X" isn't just a random number. It depends on how complex the question is (the ladder height) and how big your library is. The paper gives a formula: Frequency = (Cost of Storage) × log(Library Size + Ladder Height).

4. The "Noisy Library" (The Broken Shelf)

What if your library isn't perfect?

Loss: Some books went missing (data loss).
Pollution: Someone put fake books on the shelf (data pollution).

The paper extends its rules to this messy reality. It asks: "If we lose a key book, how much harder does the ladder get?" It turns out, if you lose a critical book, the ladder might get twice as high. The paper suggests a strategy: First, spend your budget to replace the missing critical books (compensation), then use the rest of the budget to buy shortcuts for the popular questions.

5. Grouping Questions (The "Clustering" Analogy)

Imagine you have 1 million questions. You can't write a cheat sheet for all of them.

The Smart Move: Notice that many questions are variations of the same theme. "Who is the CEO of Apple?" and "Who is the CEO of Microsoft?" are similar.
The paper suggests grouping these similar questions together. If you write a cheat sheet for the concept of "CEO," you help answer all the specific questions in that group. This makes the "storage vs. thinking" tradeoff much more efficient.

Why Does This Matter?

This isn't just about libraries. This applies to:

AI and Large Language Models: Should the AI memorize facts (store them in its "brain" weights) or look them up in a database when asked? This paper helps decide.
Database Systems: Should a company store pre-calculated reports (expensive storage) or calculate them when a user clicks a button (expensive computing power)?
Smart Cities: Should traffic lights store the "best path" for every car, or calculate it in real-time?

The Bottom Line

The paper provides a mathematical compass for the "Storage vs. Computation" struggle.

It tells us that complexity is measurable. By counting the "steps" (depth) needed to find an answer, we can predict exactly how much information is involved. With that number, we can make perfect economic decisions: Don't waste money storing answers to questions no one asks, and don't waste time calculating answers to questions asked a million times.

It turns the art of system design into a precise science of "when to think, and when to remember."

1. Problem Statement

Modern information systems face a coupled constraint: they must answer complex logical queries over large knowledge bases with low latency while operating under tight budgets for persistent storage, bandwidth, and online computation.

The Core Tension: Systems must decide what to store (as materialized views, caches, or shortcuts) and what to derive on demand.
The Gap: Existing approaches (caching, view selection, neuro-symbolic AI) often lack a unified theoretical framework that separates intrinsic semantic content (what is logically entailed) from operational shortcuts (stored derivations) and quantifies the tradeoff between storage and computation in information-theoretic terms.
Goal: To formalize "derivation depth" as a computable metric for online inferential cost, link it to algorithmic information theory (Kolmogorov complexity), and derive optimal storage-computation tradeoff strategies.

2. Methodology and Framework

The paper builds a rigorous axiomatic framework moving from semantic foundations to optimization.

A. Axiomatic Foundations (Section II)

Two-Domain Information Model: Information is modeled as a pair $(S_O, S_C)$ $(S_{O}, S_{C})$ :
- $S_O$ : Semantic/Ontological state set (the "what").
- $S_C$ : Carrier/Physical state set (the "how").
- Linked by a computable enabling mechanism $E$ .
Logical Substrate: Uses First-Order Logic with Least Fixed Points ($FO(LFP)$) over finite structures, capturing polynomial-time computation (Immerman-Vardi theorem).
Canonical Separation:
- Atom( $S_O$ ): A canonical, irredundant semantic core extracted from a knowledge base $S_O$ by removing any premise derivable from the others. This separates intrinsic content from operational shortcuts.
- Derivation Depth ($Dd(s | B)$): Defined as the height of the predecessor unfolding graph for a query $s$ relative to an available premise base $B$ . Elements in $B$ have depth 0.
Noisy Information: Extends the model to handle "noisy" bases where premises are lost (loss) or spurious premises are added (pollution).

B. Derivation Depth as an Information Metric (Section III)

The paper establishes a bridge between logical derivation cost and algorithmic information.

Derivation Traces: A derivation is encoded as a sequence of rule applications and premise pointers.
Coding Theorem: The paper proves that for generic, information-rich queries, the conditional Kolmogorov complexity $K(q | \langle B \rangle)$ $K (q ∣ ⟨ B ⟩)$ is tightly related to the derivation depth $Dd(q | B)$.
- Theorem 3.1: $K(q | \langle B \rangle) = \Theta(Dd(q | B) \cdot \log(|B| + Dd(q | B)))$ .
- Interpretation: The cost of describing a query given a base is proportional to the derivation depth multiplied by a logarithmic "addressing" term (the bits needed to index premises in the pool).
BCQ Instantiation: For Boolean Conjunctive Queries (BCQs), a compositional depth $Dd_\Sigma$ is defined, providing step-accurate bounds without needing serializability assumptions.
Semantic Locality: The framework introduces "essential core premises" to refine the complexity bound for queries that depend only on a small subset of the knowledge base.

C. Storage–Computation Tradeoffs (Section IV)

Using the depth-information correspondence, the paper derives operational design rules.

Frequency-Weighted Tradeoff:
- Cost Model: Storage cost ( $\alpha$ ) vs. Computation cost ( $\beta$ ). Let $\rho = \alpha/\beta$ .
- Break-Even Frequency ( $f_c$ ): The paper derives a critical access frequency where caching becomes optimal:
  $f_c = \Theta(\rho \cdot \log(|B| + d))$
  If a query is accessed more frequently than $f_c$ , it is cheaper to store it; otherwise, derive it on demand.
System-Wide Allocation:
- Formulates the problem of selecting a set of queries to cache under a storage budget as a Submodular Maximization problem.
- Objective: Maximize the expected reduction in derivation depth.
- Algorithm: A greedy algorithm with a $(1 - 1/e)$ -approximation guarantee is proposed.
- Scalability: Introduces semantic clustering (based on Jaccard distance of essential premises) to reduce the candidate set size for large-scale systems.

D. Extensions to Noisy Environments (Section V)

The framework is extended to handle premise loss and pollution.

Robustness: Shows that derivation depth is monotonic (adding premises never increases depth; removing premises never decreases it).
Noise-Aware Optimization:
- Derives noisy tradeoff bounds where the critical frequency depends on the size of the noisy base.
- Introduces a two-phase strategy for loss-dominated regimes: (1) Compensate by caching critical lost premises to restore feasibility, then (2) Optimize the remaining budget for depth reduction.
- Defines a "pollution exposure" score to penalize cache items that rely on spurious premises.

3. Key Contributions

Axiomatic Separation: A formal separation of intrinsic semantic content ( $Atom(S_O)$ ) from operational shortcuts, allowing for a clean distinction between logical entailment and system performance.
Depth-Information Theorem: A novel coding theorem linking Derivation Depth to Conditional Kolmogorov Complexity, proving that for generic queries, $K \approx Dd \cdot \log(\text{pool size})$ .
Break-Even Analysis: Derivation of a precise, frequency-weighted break-even scale ( $f_c$ ) for caching decisions, generalizing classical results to logical inference contexts.
Submodular Optimization: Formulating system-wide cache allocation as a submodular maximization problem, providing theoretical approximation guarantees for resource-constrained systems.
Noise-Aware Framework: Extending the theory to noisy premise bases, offering strategies for handling data loss and pollution in logical systems.

4. Key Results

Theoretical Bound: For information-rich queries, the online inference cost (depth) is asymptotically equivalent to the algorithmic information content divided by the logarithmic addressing cost.
Caching Threshold: The decision to cache a query depends on its access frequency $f_q$ relative to $\rho \log(m+d)$ . High-frequency or high-complexity queries are prime candidates for materialization.
Approximation Guarantee: The proposed greedy allocation algorithm achieves a $(1 - 1/e)$ approximation of the optimal depth reduction under a storage budget, assuming diminishing returns (submodularity).
Locality Refinement: The complexity bound can be tightened by replacing the total base size $|B|$ with the "effective" size of the premises actually used by a specific query.

5. Significance and Impact

Bridging Theory and Practice: The paper provides a rigorous information-theoretic justification for heuristic practices in database view selection, caching, and retrieval-augmented generation (RAG).
Neuro-Symbolic AI: It offers a formal lens to analyze the tradeoff between storing explicit symbolic structures (memory) and recomputing them via learned models (computation), a central tension in neuro-symbolic AI.
System Design: The derived break-even frequencies and submodular optimization algorithms provide actionable, theoretically grounded guidelines for designing efficient knowledge-based systems, particularly in scenarios with limited storage or high query latency requirements.
Robustness: By addressing noisy premises, the framework is applicable to real-world systems where data is incomplete or corrupted, moving beyond idealized theoretical models.

In summary, this paper establishes Derivation Depth as a fundamental metric that unifies logical inference cost with algorithmic information theory, enabling optimal resource allocation strategies for next-generation intelligent systems.