🔢 mathematics

Tighter Bounds for Algorithmic Complexity Estimation Using a Reusable Code-Based Block Decomposition Method

This paper introduces an enhanced Block Decomposition Method that optimizes algorithmic complexity estimation by leveraging reusable code and conditional descriptions to account for shared structures between blocks, formalizing this efficiency as "algorithmic attention" while proving its NP-hard optimization and its relationship to algorithmic mutual information.

Original authors: Eduardo Yuji Sakabe, Felipe S. Abrahão, Santiago Hernández-Orozco, Ricardo Gudwin, Hector Zenil

Published 2026-06-23

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Eduardo Yuji Sakabe, Felipe S. Abrahão, Santiago Hernández-Orozco, Ricardo Gudwin, Hector Zenil

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

Imagine you are trying to describe a massive, complex painting to a friend over the phone. You want to do it using as few words as possible.

The Old Way (BDM 1.0): The "List" Method
In the past, a method called the Block Decomposition Method (BDM) worked like this: You broke the painting into small, square tiles. For every unique tile you found, you looked up its "complexity score" in a giant dictionary.

If you saw a red tile, you said, "Red tile."
If you saw a blue tile, you said, "Blue tile."
If you saw the same red tile 50 times, you said, "Red tile, 50 times."

This was smart because it didn't waste words repeating the exact same tile. However, it had a blind spot. It treated every different tile as a completely separate, unrelated object. Even if the "Blue Tile" was just the "Red Tile" turned upside down, or if the "Green Tile" was the "Red Tile" with one pixel changed, the old method would still say, "Okay, that's a new thing. I need a whole new description for it." It missed the hidden connections.

The New Way (BDM 2.0): The "Recipe" Method
The paper introduces BDM 2.0. This new method realizes that things in the world are often related by simple rules. Instead of just listing tiles, it asks: "Can I describe this new tile by telling you how to change the old one?"

This is where the concept of Algorithmic Attention comes in. Think of it like a chef in a kitchen:

BDM 1.0 is like a chef who buys a new, separate ingredient for every single dish, even if they are just slightly different variations of the same soup.
BDM 2.0 is like a chef who realizes, "I already have the base soup. To make the spicy version, I just need to add a pinch of chili. To make the creamy version, I just need to add a splash of milk."

BDM 2.0 looks for these "pinches of chili" (short instructions or transformations) that turn one block into another. If the instruction "Turn Red Tile Upside Down" is shorter than the full description of the Blue Tile, the computer uses the instruction. It saves space by reusing the "base code."

How It Works (The "Attention" Part)
The paper calls this "Algorithmic Attention." Imagine you are writing a story.

In the old way, you would write out the full name of every character every time they appeared, even if they were related.
In the new way, you introduce the main character once (the "Representative"). Then, for their twin brother, you just write, "The twin of Character A."
The system "pays attention" to the most useful character to introduce first—the one that makes the descriptions of everyone else the shortest.

The Catch: Is It Worth It?
The paper admits there is a cost. Writing the instruction "Turn upside down" takes a few words. If the two tiles are totally different and unrelated, writing that instruction might actually take more words than just describing the second tile from scratch.

So, BDM 2.0 does a math check:

Does the "shortcut" (the instruction) save more space than the cost of explaining the shortcut?
If yes, it uses the shortcut.
If no, it falls back to the old method and describes the tile normally.

Why This Matters
The authors prove that this new method is always at least as good as the old one (it never makes the description longer unless the math is wrong). But when there is a hidden pattern or a "shared recipe" between different parts of the data, BDM 2.0 can describe the whole object much more efficiently.

It moves us from just counting how many times things repeat (statistics) to understanding how things are generated (algorithms). It's the difference between saying "This pattern repeats 100 times" and saying "This pattern is generated by a simple rule that repeats 100 times."

In a Nutshell
BDM 2.0 is a smarter way to compress data. Instead of treating every piece of a puzzle as a unique, isolated item, it looks for the "glue" that connects them. If you can explain a piece by saying "It's just Piece A with a twist," it does that. If not, it describes the piece on its own. This makes the final description shorter, but only when the pieces actually share a secret, reusable structure.

Technical Summary: Tighter Bounds for Algorithmic Complexity Estimation Using a Reusable Code-Based Block Decomposition Method

Problem Statement
Algorithmic Information Theory (AIT) posits that the complexity of an object is defined by the length of its shortest description (Kolmogorov complexity, $K(x)$ ). While the Coding Theorem Method (CTM) provides practical estimates of $K(x)$ for small objects by leveraging algorithmic probability, it is infeasible for large objects. The Block Decomposition Method (BDM) was introduced to scale CTM by decomposing large objects into small blocks, estimating the complexity of each unique block, and accounting for repetitions via Shannon entropy terms.

However, the original BDM (referred to as BDM 1.0) retains a structural limitation: it treats distinct blocks as independent descriptions. Even when distinct blocks share algorithmic information—such as being generated by related programs or transformable into one another via short mechanisms—BDM 1.0 assigns them independent complexity costs. This fails to capture regularities arising from computable mechanisms that generate or transform components, relying instead solely on exact repetition.

Methodology: BDM 2.0 and Algorithmic Attention
The paper introduces BDM 2.0, a framework that extends block decomposition by utilizing dependencies between blocks to reduce description length. The core innovation is the concept of algorithmic attention, defined as the selective allocation of descriptive resources to a subset of explanatory components (programs or blocks) that enables the most significant reduction in total description length.

Key methodological components include:

Conditional Descriptions: Instead of describing every distinct block $x_i$ $x_{i}$ independently, BDM 2.0 allows blocks (or their generating programs $p_i$ $p_{i}$ ) to be described conditionally from other selected blocks or programs. The cost is determined by the minimum of:
- Program-space conditional complexity: $\hat{K}(p_j | p_i)$
- Observation-space conditional complexity: $\hat{K}(x_j | x_i)$
Reuse Optimization: The method formulates the estimation as an optimization problem. It seeks a set of representative programs $S$ (the "attention" focus) such that the sum of their unconditional complexities plus the conditional complexities of all remaining programs (described relative to $S$ ) is minimized.
Formal Definition: The BDM 2.0 estimate is defined as:
$BDM_2(X) = \min_{P \in \mathcal{E}_X} \min_{\emptyset \neq S \subseteq P} \left( \sum_{p_i \in S} \hat{K}(p_i) + \sum_{p_j \in P \setminus S} \min_{p_i \in S} \{ \hat{K}(p_j | p_i), \hat{K}(x_j | x_i) \} \right) + \sum \log m_i$
where $m_i$ is the multiplicity of block $x_i$ .
Operationalization via CTM: The paper outlines a roadmap for implementing BDM 2.0 using CTM. This involves generating finite tables for unconditional complexities ( $\hat{K}$ ) and conditional complexities ( $\hat{K}(\cdot|\cdot)$ ) for both program representations and output blocks. It requires calibrating these scales to ensure consistency between program-level and observation-level estimates.

Key Results and Theoretical Contributions
The paper establishes several theoretical bounds and relationships:

BDM 1.0 as a Limit: Theorem 1 proves that BDM 1.0 is an admissible independent-description limit of BDM 2.0. BDM 2.0 is bounded above by BDM 1.0 plus a representation overhead term ( $C_{rep}$ ), which accounts for the discrepancy between block estimates and their shortest program generators.
Reuse Gain and Improvement: Theorem 2 demonstrates that BDM 2.0 strictly improves upon BDM 1.0 whenever the total estimated reuse gain ( $\hat{\Delta}$ ) exceeds the baseline representation overhead. The improvement is driven by the ability to replace independent descriptions with shorter conditional ones.
Connection to Mutual Information: Theorem 3 relates the theoretical reuse gain ( $\Delta$ ) to algorithmic mutual information ( $I(x:y)$ ). It shows that the total reuse gain is lower-bounded by the accumulated algorithmic mutual information between the reused programs or blocks, up to logarithmic conditioning overheads. This confirms that the gains are rooted in shared causal structure rather than statistical similarity.
Computational Complexity: The paper proves that exact optimization of the representative set $S$ is NP-hard (reducible from the weighted dominating set problem). Consequently, practical implementations must rely on heuristics, restricted candidate sets (e.g., only shortest generators), or approximation algorithms like greedy set cover.

Significance and Claims
The authors claim that BDM 2.0 represents a significant step toward making algorithmic complexity estimation more faithful to the principles of AIT.

Beyond Statistical Repetition: Unlike BDM 1.0, which captures exact repetition, BDM 2.0 captures "short mechanisms that generate or transform one component from another." This allows the method to detect structure tied to causal generators and universal compression, not just statistical fit.
Algorithmic Attention: The paper introduces "algorithmic attention" as a formal principle within Algorithmic Information Dynamics (AID). It shifts the focus from local complexity to the global efficiency of description, prioritizing components that serve as "algorithmic hubs" for other observations.
Practical Roadmap: While the paper does not present a fully implemented software suite or new experimental benchmarks, it provides a rigorous theoretical framework and a concrete operational roadmap for constructing BDM 2.0 estimators using existing CTM infrastructure. It emphasizes the necessity of validating conditional estimators to ensure they reflect genuine algorithmic mutual information rather than spurious correlations.

In conclusion, the paper argues that by incorporating reusable code-based block decomposition and conditional descriptions, BDM 2.0 offers tighter bounds on algorithmic complexity estimation, bridging the gap between local algorithmic estimates and the global structural dependencies inherent in complex systems.

Technical Summary: Tighter Bounds for Algorithmic Complexity Estimation Using a Reusable Code-Based Block Decomposition Method

More like this