Pith. sign in

REVIEW 3 major objections 1 minor 29 references

A reusable code-based block decomposition reduces description length by sharing algorithmic information across blocks.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-26 06:21 UTC pith:24LCXIUB

load-bearing objection The paper formalizes a reusable-code BDM extension with algorithmic attention and proves NP-hardness plus mutual-information ties, but the claimed tighter bounds rest on unanalyzed CTM conditional estimates. the 3 major comments →

arxiv 2606.23471 v1 pith:24LCXIUB submitted 2026-06-22 cs.IT cs.CCmath.IT

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

Eduardo Yuji Sakabe , Felipe S. Abrah\~ao , Santiago Hern\'andez-Orozco , Ricardo Gudwin , Hector Zenil This is my paper
classification cs.IT cs.CCmath.IT
keywords Block Decomposition MethodAlgorithmic ComplexityCoding Theorem MethodAlgorithmic Mutual InformationReuse OptimizationConditional ComplexityAlgorithmic Attention
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents an extension to the Block Decomposition Method that incorporates dependencies between blocks through reusable program code and conditional descriptions. This allows related components to share descriptions instead of being encoded separately, with the savings determined by the shared algorithmic information. The extension is cast as a reuse optimization problem whose exact solution is NP-hard, and it is shown to improve on the original BDM under stated conditions while relating the gains to algorithmic mutual information. A practical implementation path is outlined using estimates from the Coding Theorem Method.

Core claim

We introduce a version of BDM in which dependencies between blocks are utilized to reduce the length of the description based on reusable program code in the decomposition of an object, and on conditional descriptions capable of accounting for shared structure between observations. We formalize this allocation of descriptive resources as algorithmic attention. Repeated or related components need not be described independently, and the resulting reduction in description length is governed by the amount of shared algorithmic information.

What carries the argument

The reusable code-based block decomposition with algorithmic attention, which minimizes total description length by allocating shared code across blocks according to conditional complexity.

Load-bearing premise

Accurate conditional algorithmic complexity estimates between blocks can be obtained from CTM-derived values at a scale sufficient to realize the claimed reductions.

What would settle it

An explicit computation on a string with known shared structure where the reusable version yields a longer or equal description length than standard BDM, or where the conditional estimates produce no net saving.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Exact optimization of block reuse is NP-hard.
  • Conditions exist under which the method strictly improves upon independent block descriptions.
  • Achievable gains are bounded by algorithmic mutual information between blocks.
  • The new formulation is provably related to the earlier BDM version.
  • Implementation is possible using CTM-derived complexity and conditional complexity estimates.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Approximation algorithms will be needed for any practical deployment on large objects.
  • The approach could extend to other compression or complexity estimators that currently treat segments independently.
  • Testing on strings with controlled repetition patterns would quantify the typical size of the savings.
  • The method supplies a formal link between attention-like resource allocation and algorithmic information theory.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 1 minor

Summary. The paper extends the Block Decomposition Method (BDM) by incorporating dependencies between blocks via reusable program code and conditional descriptions, formalizing the allocation of descriptive resources as 'algorithmic attention'. It formulates the approach as a reuse optimization problem, proves that exact optimization is NP-hard, derives conditions under which the extension improves upon independent block descriptions, relates the gains to algorithmic mutual information, proves the relationship to the prior BDM formulation, and supplies a roadmap for implementation that substitutes CTM-derived values for both K(x) and the conditional terms K(x|y).

Significance. If the central claims hold, the work would supply a principled way to obtain strictly tighter upper bounds on algorithmic complexity for objects with shared structure, extending the range of CTM/BDM beyond what independent block descriptions allow. The formalization of algorithmic attention and the explicit link to algorithmic mutual information are potentially useful for downstream applications that rely on accurate complexity estimates.

major comments (3)
  1. [Implementation roadmap] Implementation roadmap section: the claim that the method yields tighter bounds rests on substituting CTM-derived estimates for the conditional complexities K(x|y) that govern the savings; no error bounds, bias analysis, or scaling argument is supplied showing that the approximation error remains smaller than the mutual-information savings for objects beyond direct CTM range.
  2. [Reuse optimization formulation] The NP-hardness proof for the reuse optimization problem (stated in the abstract) is load-bearing for the practical roadmap; the manuscript must exhibit the reduction and confirm that the hardness result applies to the version that uses CTM-derived conditional estimates rather than oracles.
  3. [Improvement conditions] Conditions for improvement over independent descriptions (abstract) are derived in terms of algorithmic mutual information, but the manuscript must verify that these conditions remain sufficient once the conditional terms are replaced by their CTM approximations.
minor comments (1)
  1. [Formal definition] Notation for algorithmic attention should be introduced with an explicit equation relating it to the difference between independent and conditional description lengths.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each major comment below, indicating planned revisions where appropriate. The work focuses on formalizing the extension and its theoretical properties; practical approximation analyses are noted as directions for follow-up.

read point-by-point responses

  1. Referee: [Implementation roadmap] Implementation roadmap section: the claim that the method yields tighter bounds rests on substituting CTM-derived estimates for the conditional complexities K(x|y) that govern the savings; no error bounds, bias analysis, or scaling argument is supplied showing that the approximation error remains smaller than the mutual-information savings for objects beyond direct CTM range.

    Authors: We agree that the manuscript supplies no explicit error bounds or scaling analysis for CTM approximations of the conditional terms. The roadmap is presented at a conceptual level, relying on the exact-case improvement conditions derived from algorithmic mutual information. In revision we will add a clarifying paragraph stating that practical gains require the approximation error to be smaller than the mutual-information savings and referencing existing CTM convergence results for small strings; a full empirical scaling study lies outside the current theoretical scope. revision: partial

  2. Referee: [Reuse optimization formulation] The NP-hardness proof for the reuse optimization problem (stated in the abstract) is load-bearing for the practical roadmap; the manuscript must exhibit the reduction and confirm that the hardness result applies to the version that uses CTM-derived conditional estimates rather than oracles.

    Authors: The NP-hardness result is proven for the exact optimization problem with oracle access to the complexity function. We will revise the manuscript to include the explicit reduction (from the minimum set cover problem) so that the proof is self-contained. Because the combinatorial structure of the decision problem is independent of the particular values supplied for the conditional terms, the hardness carries over when those values are replaced by any fixed estimates such as CTM outputs. revision: yes

  3. Referee: [Improvement conditions] Conditions for improvement over independent descriptions (abstract) are derived in terms of algorithmic mutual information, but the manuscript must verify that these conditions remain sufficient once the conditional terms are replaced by their CTM approximations.

    Authors: The improvement conditions are stated and proven for the exact conditional complexities. With CTM approximations the same conditions remain sufficient provided the estimation error is bounded by a quantity smaller than the mutual-information term; we will add a short remark in the revised text making this dependence explicit and noting that it follows directly from the triangle inequality applied to the description lengths. revision: partial

Circularity Check

0 steps flagged

No circularity; new formal quantities and optimization problem defined independently of inputs

full rationale

The paper introduces algorithmic attention and a reuse optimization problem as new constructs, derives conditions for improvement over independent BDM descriptions, relates gains to algorithmic mutual information, and proves a relationship to prior BDM. These steps are definitional and relational rather than reducing any claimed result to a fitted parameter or self-citation by construction. The implementation roadmap invokes CTM-derived estimates but does not equate the new bounds to those estimates; the derivation remains self-contained as a theoretical extension without load-bearing self-referential steps.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the standard axioms of algorithmic probability and Kolmogorov complexity (used to define CTM and conditional complexity) plus the modeling choice that shared structure between blocks can be captured by conditional program descriptions. No free parameters or invented physical entities are introduced; algorithmic attention is a new descriptive concept rather than a new entity with independent evidence.

axioms (2)
  • standard math Kolmogorov complexity and algorithmic probability are well-defined and can be approximated via the Coding Theorem Method for small strings.
    Invoked when the abstract states that the method uses 'CTM-derived complexity and conditional complexity estimates'.
  • domain assumption The description length of a block decomposition can be reduced by reusing program code across blocks when conditional complexity is lower than unconditional complexity.
    This is the modeling premise that justifies the reusable-code extension and the claimed improvement over independent descriptions.
invented entities (1)
  • algorithmic attention no independent evidence
    purpose: Formal name for the allocation of descriptive resources that reuses program code across related blocks.
    New term introduced in the abstract to describe the reuse mechanism; no independent falsifiable prediction is supplied.

pith-pipeline@v0.9.1-grok · 5752 in / 1608 out tokens · 21166 ms · 2026-06-26T06:21:47.012944+00:00 · methodology

0 comments
read the original abstract

The Block Decomposition Method (BDM) was introduced as an alternative to popular lossless compression methods such as LZW for estimating algorithmic complexity from the principles of algorithmic probability and classical information theory. It extends the Coding Theorem Method (CTM) from small objects to larger ones by combining local estimates of algorithmic complexity with a global account of repetition based on Shannon entropy. Here, we introduce a version of BDM in which dependencies between blocks are utilized to reduce the length of the description based on reusable program code in the decomposition of an object, and on conditional descriptions capable of accounting for shared structure between observations. We formalize this allocation of descriptive resources as algorithmic attention. Repeated or related components need not be described independently, and the resulting reduction in description length is governed by the amount of shared algorithmic information. We formulate this extension as a reuse optimization problem, show that exact optimization is NP-hard, derive conditions under which it improves upon independent descriptions, relate the achievable gains to algorithmic mutual information, prove the relationship with the previous BDM version, and provide a roadmap for its implementation using CTM-derived complexity and conditional complexity estimates.

Figures

Figures reproduced from arXiv: 2606.23471 by Eduardo Yuji Sakabe, Felipe S. Abrah\~ao, Hector Zenil, Ricardo Gudwin, Santiago Hern\'andez-Orozco.

Figure 1
Figure 1. Figure 1: BDM 1.0 independent descriptions versus BDM 2.0 algorith￾mic attention and reuse. BDM 1.0 operates at the level of distinct blocks, treating their descriptions as independent and summing the estimated complex￾ities of each unique block. BDM 2.0 extends this view by allowing dependencies to be represented in both program-complexity space (KP ) and object-complexity space (KX). The quantities I(p2 : p3) and … view at source ↗
Figure 2
Figure 2. Figure 2: Conditional descriptions can be short in observation or pro￾gram space. (a) Distinct 4 × 4 blocks satisfy x2 = x T 1 and x4 = comp(x3). Because transposition and bitwise complementation are fixed computable trans￾formations, the observation-level costs Kˆ (x2 | x1) and Kˆ (x4 | x3) can be small when these operations are represented by the estimator. (b) ECA Rules 90 = 010110102 and 91 = 010110112 differ on… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 4 canonical work pages · 1 internal anchor

  1. [1]

    Characterizing Learning in Deep Neural Networks using Tractable Algorithmic Complexity Analysis

    Pedram Bakhtiarifard, Sophia N. Wilson, Mahmoud Afifi, Jonathan Wenshøj, and Raghavendra Selvan. Characterizing Learning in Deep Neu- ral Networks using Tractable Algorithmic Complexity Analysis, May 2026. arXiv:2605.15551 [cs.LG]

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  2. [2]

    Gregory J. Chaitin. On the Length of Programs for Computing Finite Binary Sequences: statistical considerations.Journal of the ACM (JACM), 16(1):145–159, January 1969

    1969

  3. [3]

    V. Chvatal. A Greedy Heuristic for the Set-Covering Problem.Mathematics of Operations Research, 4(3):233–235, 1979

    1979

  4. [4]

    Attention, please! A survey of neural attention models in deep learning.Artificial Intelligence Review, 55(8):6037–6124, 2022

    Alana de Santana Correia and Esther Luna Colombini. Attention, please! A survey of neural attention models in deep learning.Artificial Intelligence Review, 55(8):6037–6124, 2022

    2022

  5. [5]

    Jean-Paul Delahaye and Hector Zenil. Numerical evaluation of algorithmic complexity for short strings: A glance into the innermost structure of ran- domness.Applied Mathematics and Computation, 219(1):63–77, September 2012

    2012

  6. [6]

    Garey and David S

    Michael R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman, 1979

    1979

  7. [7]

    Human behavioral complexity peaks at age 25

    Nicolas Gauvrit, Hector Zenil, Fernando Soler-Toscano, Jean-Paul Dela- haye, and Peter Brugger. Human behavioral complexity peaks at age 25. PLOS Computational Biology, 13(4):e1005408, 2017

    2017

  8. [8]

    Shannon Information and Kolmogorov Complexity, 2004

    Peter Grunwald and Paul Vitanyi. Shannon Information and Kolmogorov Complexity, 2004. arXiv:cs/0410002

    work page arXiv 2004

  9. [9]

    Abrah˜ ao, and Hector Zenil

    Alberto Hern´ andez-Espinosa, Luan Ozelim, Felipe S. Abrah˜ ao, and Hector Zenil. SuperARC: a test for artificial superintelligence based on compressed 28 modelling, recursive prediction and problem complexity.Nature Commu- nications, 17(1):4885, 2026

    2026

  10. [10]

    Kiani, and Jesper Tegn´ er

    Santiago Hern´ andez-Orozco, Hector Zenil, J¨ urgen Riedel, Adam Uccello, Narsis A. Kiani, and Jesper Tegn´ er. Algorithmic Probability-Guided Ma- chine Learning on Non-Differentiable Spaces.Frontiers in Artificial Intel- ligence, 3, January 2021

    2021

  11. [11]

    A. N. Kolmogorov. Three approaches to the quantitative definition of infor- mation *.International Journal of Computer Mathematics, 2(1-4):157–168, January 1968. eprint: https://doi.org/10.1080/00207166808803030

    work page doi:10.1080/00207166808803030 1968

  12. [12]

    Leonid A. Levin. Laws of information conservation (nongrowth) and as- pects of the foundation of probability theory.Problemy Peredachi Infor- matsii, 10(3):30–35, 1974

    1974

  13. [13]

    Leonid A. Levin. On a concrete method of assigning complexity measures. InDoklady Akademii Nauk, volume 234, pages 536–539. Russian Academy of Sciences, 1977. Issue: 3

    1977

  14. [14]

    Texts in Computer Science

    Ming Li and Paul Vit´ anyi.An Introduction to Kolmogorov Complexity and Its Applications. Texts in Computer Science. Springer International Publishing, Cham, 2019

    2019

  15. [15]

    Yuji Sakabe, Felipe S

    Eduardo Y. Yuji Sakabe, Felipe S. Abrah˜ ao, Alexandre Sim˜ oes, Esther Colombini, Paula Costa, Ricardo Gudwin, and Hector Zenil. Binarized neural networks converge toward algorithmic simplicity: empirical support for the learning-as-compression hypothesis.Frontiers in Computational Neuroscience, 20, May 2026

    2026

  16. [16]

    Neural Attention Models in Deep Learning: Survey and Taxonomy, 2021

    Alana Santana and Esther Colombini. Neural Attention Models in Deep Learning: Survey and Taxonomy, 2021. arXiv:2112.05909 [cs.LG]

    work page arXiv 2021

  17. [17]

    Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines.PLOS ONE, 9(5):e96223, 2014

    Fernando Soler-Toscano, Hector Zenil, Jean-Paul Delahaye, and Nicolas Gauvrit. Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines.PLOS ONE, 9(5):e96223, 2014

    2014

  18. [18]

    R. J. Solomonoff. A formal theory of inductive inference. Part I.Informa- tion and Control, 7(1):1–22, March 1964

    1964

  19. [19]

    R. J. Solomonoff. A formal theory of inductive inference. Part II.Informa- tion and Control, 7(2):224–254, June 1964

    1964

  20. [20]

    Attention is All you Need

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need. InAdvances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017

    2017

  21. [21]

    A Technique for High-Performance Data Compression.Computer, 17(6):8–19, June 1984

    Welch. A Technique for High-Performance Data Compression.Computer, 17(6):8–19, June 1984. 29

    1984

  22. [22]

    A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions.Entropy, 22(6):612, June 2020

    Hector Zenil. A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions.Entropy, 22(6):612, June 2020

    2020

  23. [23]

    Kiani, Fernando Soler- Toscano, Antonio Rueda-Toicen, and Jesper Tegn´ er

    Hector Zenil, Santiago Hern´ andez-Orozco, Narsis A. Kiani, Fernando Soler- Toscano, Antonio Rueda-Toicen, and Jesper Tegn´ er. A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity.Entropy, 20(8):605, August 2018

    2018

  24. [24]

    Kiani, Alyssa Adams, Felipe S

    Hector Zenil, Narsis A. Kiani, Alyssa Adams, Felipe S. Abrah˜ ao, Antonio Rueda-Toicen, Allan A. Zea, Luan Ozelim, and Jesper Tegn´ er. Minimal algorithmic information loss methods for dimension reduction, feature se- lection and network sparsification.Information Sciences, 720:122520, 2025

    2025

  25. [25]

    Kiani, and Jesper Tegn´ er.Algorithmic Information Dynamics: A Computational Approach to Causality with Applications to Living Systems

    Hector Zenil, Narsis A. Kiani, and Jesper Tegn´ er.Algorithmic Information Dynamics: A Computational Approach to Causality with Applications to Living Systems. Cambridge University Press, 2023

    2023

  26. [26]

    Kiani, Allan A

    Hector Zenil, Narsis A. Kiani, Allan A. Zea, and Jesper Tegn´ er. Causal deconvolution by algorithmic generative models.Nature Machine Intelli- gence, 1(1):58–66, January 2019. Publisher: Nature Publishing Group

    2019

  27. [27]

    Asymptotic Intrinsic Universality and Nat- ural Reprogrammability by Behavioural Emulation

    Hector Zenil and J¨ urgen Riedel. Asymptotic Intrinsic Universality and Nat- ural Reprogrammability by Behavioural Emulation. In Andrew Adamatzky, editor,Advances in Unconventional Computing: Volume 1: Theory, pages 205–220. Springer International Publishing, Cham, 2017

    2017

  28. [28]

    Two-dimensional Kolmogorov complexity and an empirical vali- dation of the Coding theorem method by compressibility.PeerJ Computer Science, 1:e23, September 2015

    Hector Zenil, Fernando Soler-Toscano, Jean-Paul Delahaye, and Nicolas Gauvrit. Two-dimensional Kolmogorov complexity and an empirical vali- dation of the Coding theorem method by compressibility.PeerJ Computer Science, 1:e23, September 2015

    2015

  29. [29]

    Ziv and A

    J. Ziv and A. Lempel. A universal algorithm for sequential data com- pression.IEEE Transactions on Information Theory, 23(3):337–343, May 1977. 30 Supplementary Information A CTM State-Space Counts The Coding Theorem Method (CTM) relies on exhaustive enumeration of small Turing machines. For machines withnstates andksymbols, each state-symbol pair require...

    1977