Pith. sign in

REVIEW 3 major objections 5 minor 30 references

A theory of incremental compression

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The paper claims that incrementally extracting the shortest features of a data string partitions its information into independent pieces and reaches the optimal Kolmogorov complexity to within logarithmic overhead.

desk verdict The theoretical decomposition result is sound and genuinely new; the computable ALICE algorithm does not inherit the near-optimality guarantee, so the abstract overreaches. read the letter →

arxiv 1908.03781 v2 pith:WJKYFU2M submitted 2019-08-10 cs.IT cs.LGmath.IT

Arthur Franz , Oleksandr Antonenko , Roman Soletskyi This is my paper · ORCID
classification cs.ITcs.LGmath.IT MSC 68Q3094A1703D32
keywords incrementalcompressionKolmogorovcomplexityfeatureextractionautoencoderalgorithmicrandomnessinformationtheorylosslessALICE
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to show that compression can be done piece by piece, with no real loss. It defines a 'feature' of a string as a short program that, together with a shorter 'residual' description, reconstructs the original string. The central claim is that if at every step you take the shortest possible feature, then the sum of the feature lengths plus the complexity of the final residual equals the Kolmogorov complexity of the string, up to a logarithmic overhead. That would mean a greedy, incremental search for features is nearly as good as the theoretically optimal one-shot compression. The paper also gives ALICE, a computable version, and connects features to algorithmic randomness tests, arguing that features formalize what it means for a string to have a 'property.'

What carries the argument

The central object is the autoencoder pair (f, f'), where the descriptive map f' compresses the string x into a residual r and the feature f reconstructs x from r, under the compression condition l(f) + l(r) < l(x). A 'shortest feature' f* is a feature of minimal length; the paper proves such features are incompressible, contain almost no mutual information with their residual, and carry no superfluous information about x. Iterating the shortest-feature selection on successive residuals yields the partition; the key identity is K(x) = sum l(f*_i) + K(r_s) + O(s log l(x)) from Theorem 3.6. The computable ALICE algorithm replaces the incomputable shortest-feature search by a dovetailed enumeration of autoencoders, and its runtime is bounded by the explicit sum in Theorem 4.1.

What would settle it

Take a family of strings such as 1^n 0 y whose shortest feature is known analytically, run Greedy-ALICE's SearchAutoencoder on them, and compare the found feature's length with the true shortest-feature length. If the gap d = l(f) - l(f*) is larger than O(log l(x)), or if any single output description length violates the bound of Theorem 3.6 for every constant C, the near-optimality claim would fail.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central discovery is that a string x can be rewritten as x = f*_1(f*_2(... f*_s(r_s)...)), where each f*_i is a shortest feature of the current residual and r_s is the final incompressible residual. The description length of this decomposition satisfies Theorem 3.6: K(x) = sum_{i=1}^s l(f*_i) + K(r_s) + O(s log l(x)). Together with Theorem 3.1, showing that shortest features are incompressible, and Theorem 3.3, showing that features and residuals contain almost no mutual information, this means the information in x is partitioned into nearly disjoint, incompressible pieces. The authors further show that for strings compressible by a fixed factor, the shortest features have constant length and the number of steps is O(log l(x)), making the overhead small. For general strings, Theorem 3.6 remains the headline: incremental extraction of shortest features is near-optimal compression.

Load-bearing premise

The guarantee that the greedy scheme is near-optimal depends on actually selecting the shortest feature at every step, but the computable algorithm searches by total autoencoder length, so the first autoencoder it finds need not be a shortest feature; the paper itself concedes that shortest features are incomputable.

Editorial extensions

If this is right

  • If Theorem 3.6 is right, a greedy, no-backtracking search for the shortest feature at each step produces a description of the string whose length misses the Kolmogorov complexity by at most O(s log l(x)); for well-compressible strings this shrinks to O(log l(x)).
  • The features obtained by incremental compression are pairwise independent in the algorithmic-information sense, so the information in the string is genuinely partitioned rather than redundantly described.
  • For strings compressible by a fixed factor b > 1, every shortest feature is bounded by a constant length and the number of steps is O(log l(x)), so the whole decomposition becomes computationally tractable and the overhead stays small.
  • ALICE provides a computable procedure whose running time is bounded by the expression in Theorem 4.1, giving a concrete time-complexity analogue of universal search adapted to incremental features.
  • The correspondence with algorithmic randomness tests means features are not just a compression device: they are a formal way to identify the non-random 'properties' of a string.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the independence result carries over to practical settings, layer-by-layer training of stacked autoencoders has a principled justification: each layer should capture one incompressible feature and the residual should contain no information about it; this is measurable by estimating mutual information between layer weights and residual activations.
  • The gap d = l(f) - l(f*) quantifies how much description length a model class wastes by not being truly minimal, offering a concrete cost for using a restricted family of functions rather than a general-purpose search.
  • Combining the framework with the layered prefix-coding technique that the paper notes is not straightforwardly adapted might remove even the logarithmic overhead and make incremental compression exactly optimal rather than near-optimal.
  • The theory predicts that in trained deep networks that generalize well, the algorithmic mutual information between features extracted at different layers should be near zero; datasets that violate this would be poor candidates for this compression view.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper develops a theory of incremental lossless compression based on algorithmic information theory. It defines a feature f of a string x as a program such that x = f(r) for some residual r with l(f) + l(r) < l(x), and a shortest feature as one minimizing l(f). The central theoretical result (Theorem 3.6) states that if at each step of a greedy iteration one selects a shortest feature f_i* and then compresses the residual, the total description length sum_i l(f_i*) + K(r_s) equals K(x) up to O(s log l(x)). Supporting results show that shortest features are incompressible (Theorem 3.1), their number grows at most polynomially (Theorem 3.2), a shortest feature and its residual carry negligible mutual information (Theorem 3.3 and Corollary 3.1), and the pair contains no superfluous information (Theorem 3.4). The paper introduces b-features to bound the number of steps, presents two computable algorithms (Greedy-ALICE and ALICE) with a time-complexity bound (Theorem 4.1), reports on the WILLIAM implementation, and connects features to Martin-Löf randomness tests (Theorems 5.1 and 5.2).

Significance. If the theoretical results hold, the paper gives a novel decomposition of Kolmogorov complexity into features and a residual, with a proof that greedy extraction of shortest features is near-optimal up to logarithmic factors when the number of steps is controlled. This is a parameter-free derivation from standard algorithmic information theory, not a fitted model, and the connection to Martin-Löf randomness tests gives features a principled interpretation as formalized non-random properties. The theoretical core is internally consistent on my reading. However, the computable algorithms do not implement shortest-feature selection, and the proof of Theorem 3.6 relies on an unformalized concatenation convention. These gaps mean that the paper's computable claims are substantially weaker than the abstract suggests and require either additional analysis or careful qualification.

major comments (3)
  1. [Section 4.1, Algorithm 1 (SearchAutoencoder), and Theorem 4.1] Greedy-ALICE and ALICE do not provably select shortest features. SearchAutoencoder enumerates autoencoders a = f'f by total length l(a) = l(f') + l(f) and returns the first one satisfying l(f) + l(r) < l(x); minimal total autoencoder length is not minimal feature length, and the dovetail schedule means the first return is determined by runtime rather than by l(f). Consequently the penalty d = l(f) - l(f*) from Theorem 3.3 can be large, and the optimality bound of Theorem 3.6 (eq. 42) does not carry over to the returned description. Section 4 itself notes that shortest features are incomputable, and Theorem 4.1 only bounds the time needed to find some description, not the distance of that description from optimality. The abstract and Section 6 present ALICE as the computable realization of the near-optimal scheme; that claim is unsupported unless a bound on d for the actual search order is proved or all near-optimality claims are restricted to the ideal shortest-feature scheme.
  2. [Section 3.2, proof of Theorem 3.6] The proof that D_s := <s, r_s, f*_s ... f*_1> is a description of x relies on the assertion that U(bar r_s f*_s) halts with the input head at the start of the remainder f*_{s-1} ... f*_1. This is not justified by the definition U(<y,<i,q>>) = T_i(<y,q>) with <x,y> = xy, since strings are not self-delimiting by default and the concatenated encoding may be ambiguous. The theorem can survive if each feature is taken from a prefix-free program set and r_s is self-delimiting encoded, but this needs to be stated and proved because eq. (42) is the load-bearing optimality result.
  3. [Abstract, Section 3.6, and Theorem 3.5] The abstract's 'close to optimal' and 'pairwise independent' are stronger than what is proved. Theorem 3.6 has error term O(s log l(x)) with no bound on s for the first scheme; as Remark 3.1 shows, s can be O(l(x)), making the error O(l(x) log l(x)), which is not close to K(x). The b-feature scheme bounds s = O(log l(x)), but Theorem 3.9 gives l(D_s) <= bK(x) + O(log l(x)), which is close to K(x) only when b is close to 1. Similarly, Theorem 3.5 gives I(f*_i : f*_j) = O(|i - j| log l(x)), not a distance-independent independence bound. These qualifications should appear wherever near-optimality or independence is claimed.
minor comments (5)
  1. [Section 2.2, prefix codes] The definitions of E1 and E2 are garbled: 'E1(x) = x = 1^{l(x)}0x' should presumably be 'E1(x) = 1^{l(x)}0x', and E2(x) = l(x)x is not self-delimiting as written; the proof of Lemma 3.2 uses a code of length l(r) + 2l(l(r)), so the definition should be made explicit.
  2. [Lemma 3.4 proof] In the displayed chain of equalities there is a '> K(y|x)' where an equality or '>=' is intended; please correct this typo.
  3. [Section 4.3] The WILLIAM implementation is described only anecdotally and is not connected to Theorems 3.6 or 4.1; if kept, it should be labeled as illustrative rather than as evidence for the theoretical claims.
  4. [Algorithm 2] The line 'run SearchAutoencoderRecursively(status[a]) for 1 step' is confusing because status[a] is a tuple <r, F>; clarify the variable naming and the type of status entries.
  5. [Section 6.2] The sentence 'Even though it is hard to imagine compressible data without any features at all, it might exist in abundance' should be rephrased, since the antecedent is 'data' rather than 'features'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central theorem is derived from standard algorithmic information theory, not from its own conclusion.

full rationale

The paper's load-bearing result, Theorem 3.6, is obtained by induction from Theorem 3.4, which in turn is proved from Lemma 3.1, Corollary 3.1, and Theorem 3.2. None of these steps sets its conclusion as an input: features are defined purely by reconstruction and the compression condition l(f)+l(f'(x))<l(x) (Def. 2.1); Kolmogorov complexity is the standard prefix-complexity minimum (eq. 3); and the inequalities in Theorems 3.1-3.4 are derived, not assumed. The shortest-feature decomposition is not forced by definition: Lemma 3.1, which identifies l(f*) with K(x|r), is a non-trivial argument using the compression condition to show that any shorter program would itself be a feature. Self-citations appear ([5], [6], [7]) but they are not load-bearing: the theory is re-proved in this paper, and footnote 3 explicitly corrects errors in the earlier conference paper. The WILLIAM demonstrations in [6,7] are cited only as practical illustrations and are not inputs to the main theorems. The Martin-Löf connection in Theorems 5.1-5.2 is an independent two-way construction rather than a renaming of the target result. Any gap between the ideal shortest-feature scheme and the computable ALICE algorithm is a correctness or computability caveat acknowledged in Section 4, not a circularity.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

No data fitting is involved in the central claim. The b parameter is an algorithmic choice, not a fitted value, and no new physical entities are introduced; feature, descriptive map and residual are formal definitions rather than empirical postulates.

free parameters (1)
  • b (compression factor)
    Introduced in Definition 3.1 to bound the number of compression steps by O(log l(x)). It is a user-chosen constant, not fitted to data, and it does not appear in the central Theorem 3.6.
assumptions (6)
  • standard math Strings are finite binary strings and K is prefix Kolmogorov complexity relative to a fixed universal prefix Turing machine U.
    Section 2.2 sets up this standard framework following Li and Vitanyi [18].
  • standard math The invariance theorem and standard bounds such as K(x) <= l(x) + K(l(x)) + O(1) hold.
    Used throughout Theorems 3.1, 3.3 and 3.4 as unstated background facts from [18].
  • standard math Symmetry of algorithmic information holds to logarithmic precision.
    Invoked in Lemma 3.3 and Theorem 3.5, citing [18, Lemma 3.9.2].
  • standard math The Kolmogorov-Levin theorem holds to logarithmic precision for prefix complexity.
    Used in Corollary 3.1, citing [26, Theorem 21].
  • domain assumption The universal machine U parses concatenated inputs so that a feature execution halts with the input head at the start of the remainder.
    Assumed in the proof of Theorem 3.6 for the delimiter-free encoding D_s; this convention is asserted but not proved in detail.
  • standard math Martin-Löf tests are lower semicomputable functions with the cardinality condition of Definition 5.1, and a standard enumeration of tests exists.
    Section 5 relies on these definitions and on standard properties of randomness tests from [18].

how reviews work

0 comments
Cite this review

Pith. "Pith review of A theory of incremental compression." pith.science (2026). https://pith.science/paper/WJKYFU2M

@misc{pith2026190803781,
  author       = {Pith},
  title        = {Pith review of: A theory of incremental compression},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WJKYFU2M}},
  note         = {Machine review of arXiv:1908.03781}
}
read the original abstract

The ability to find short representations, i.e. to compress data, is crucial for many intelligent systems. We present a theory of incremental compression showing that arbitrary data strings, that can be described by a set of features, can be compressed by searching for those features incrementally, which results in a partition of the information content of the string into a complete set of pairwise independent pieces. The description length of this partition turns out to be close to optimal in terms of the Kolmogorov complexity of the string. Exploiting this decomposition, we introduce ALICE - a computable ALgorithm for Incremental ComprEssion - and derive an expression for its time complexity. Finally, we show that our concept of a feature is closely related to Martin-L\"of randomness tests, thereby formalizing the meaning of "property" for computable objects.

Figures

Figures reproduced from arXiv: 1908.03781 by the authors.

Figure 1
Figure 1. An autoencoder. Examples. Consider a string of the form x = 1n0y (where 1 n := n times z }| { 1 . . . 1). Then, a descriptive map could be a function computing the number n of initial ones and copying y to the residual description, f 0 1 (x) = hn, yi =: r. A feature could be a function taking the residual r = hn, yi which is a combination of number of ones n and the rest of string y and mapping it back to x, f1(r) =… view at source ↗
Figure 2
Figure 2. A string x is incrementally compressed, i.e. its description length decreases every step until the shortest description K(x) is approximated by Ps i=1 l (fi) + K (rs), see Theorem 3.6 below. The compression condition l (fi) + l (ri) < l (ri−1) ensures that the description length of each residual ri decreases. 2.2. Preliminaries Consider strings made up of elements of the set B = {0, 1} with  denoting the empty stri… view at source ↗
Figure 3
Figure 3. The proof strategy. a) Since x is computed from shortest feature f ∗ and residual r, f ∗(r) = x, all its information is contained in the union of f ∗ and r. b) Theorem 3.3 and Corollary 3.1 show that f ∗ and r do not contain mutual information and therefore do not overlap. c) Theorem 3.4 shows that f ∗ and r do not contain information beyond what is necessary to compute x. It follows that the information in x is par… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 26 canonical work pages

  1. [1]

    A new look at the statistical model identification.Automatica, 19(6):465–471, 1978

    Hirotugu Akaike. A new look at the statistical model identification.Automatica, 19(6):465–471, 1978

    work page 1978

  2. [2]

    Horace B. Barlow. Possible principles underlying the transformation of sensory messages.Sensory communi- cation, 1:217–234, 1961

    work page 1961

  3. [3]

    Compression of data streams down to their information content

    George Barmpalias and Andrew Lewis-Pye. Compression of data streams down to their information content. IEEE Transactions on Information Theory, 65(7):4471–4485, 2019

    work page 2019

  4. [4]

    Bishop.Pattern recognition and machine learning

    Christopher M. Bishop.Pattern recognition and machine learning. Springer, 2006

    work page 2006

  5. [5]

    Some theorems on incremental compression

    Arthur Franz. Some theorems on incremental compression. InInternational Conference on Artificial General Intelligence, pages 74–83. Springer, 2016

    work page 2016

  6. [6]

    Introducing WILLIAM: a system for inductive inference based on the theory of incremental compression

    Arthur Franz, Michael Löffler, Alexander Antonenko, Victoria Gogulya, and Dmytro Zaslavskyi. Introducing WILLIAM: a system for inductive inference based on the theory of incremental compression. InInternational Conference on Computer Algebra and Information Technology, 2018

    work page 2018

  7. [7]

    WILLIAM: A monolithic approach to AGI

    Arthur Franz, Victoria Gogulya, and Michael Löffler. WILLIAM: A monolithic approach to AGI. InInterna- tional Conference on Artificial General Intelligence, pages 44–58. Springer, 2019

    work page 2019

  8. [8]

    Hinton and Ruslan R

    Geoffrey E. Hinton and Ruslan R. Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 313(5786):504–507, 2006

    work page 2006

Show all 30 references
  1. [9]

    Hinton, Simon Osindero, and Yee-Whye Teh

    Geoffrey E. Hinton, Simon Osindero, and Yee-Whye Teh. A fast learning algorithm for deep belief nets.Neural computation, 18(7):1527–1554, 2006

    2006

  2. [10]

    The fastest and shortest algorithm for all well-defined problems.International Journal of Foundations of Computer Science, 13(3):431–443, June 2002

    Marcus Hutter. The fastest and shortest algorithm for all well-defined problems.International Journal of Foundations of Computer Science, 13(3):431–443, June 2002. URLhttp://www.hutter1.net/ai/pfastprg. htm

    2002

  3. [11]

    Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Prob- ability

    Marcus Hutter. Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Prob- ability. Springer, Berlin, 2005. ISBN 3-540-22139-5. doi: 10.1007/b138233. 300 pages, http://www.hutter1.net/ai/uaibook.htm

    2005 doi

  4. [12]

    Gauch Jr.Scientific method in practice

    Hugh G. Gauch Jr.Scientific method in practice. Cambridge University Press, 2003

    2003

  5. [13]

    Kinship categories across languages reflect general communicative principles

    Charles Kemp and Terry Regier. Kinship categories across languages reflect general communicative principles. Science, 336(6084):1049–1054, 2012

    2012

  6. [14]

    Knill and Whitman Richards.Perception as Bayesian inference

    David C. Knill and Whitman Richards.Perception as Bayesian inference. Cambridge University Press, 1996

    1996

  7. [15]

    quantity of information

    Andrei N. Kolmogorov. Three approaches to the definition of the concept "quantity of information".Problemy peredachi informatsii, 1(1):3–11, 1965

    1965

  8. [16]

    Universal intelligence: A definition of machine intelligence

    Shane Legg and Marcus Hutter. Universal intelligence: A definition of machine intelligence. Minds and machines, 17(4):391–444, 2007

    2007

  9. [17]

    Universal sequential search problems.Problemy Peredachi Informatsii, 9(3):115–116, 1973

    Leonid A Levin. Universal sequential search problems.Problemy Peredachi Informatsii, 9(3):115–116, 1973

    1973

  10. [18]

    Springer, 2009

    Ming Li and Paul MB Vitányi.An introduction to Kolmogorov complexity and its applications. Springer, 2009

    2009

  11. [19]

    David J. C. MacKay.Information theory, inference and learning algorithms. Cambridge university press, 2003. 23

    2003

  12. [20]

    Olshausen and David J

    Bruno A. Olshausen and David J. Field. Emergence of simple-cell receptive field properties by learning a sparse code for natural images.Nature, 381(6583):607, 1996

    1996

  13. [21]

    Making universal induction efficient by specialization

    Alexey Potapov and Sergey Rodionov. Making universal induction efficient by specialization. InInternational Conference on Artificial General Intelligence, pages 133–142. Springer, 2014

    2014

  14. [22]

    Modeling by shortest data description.Automatica, 14(5):465–471, 1978

    Jorma Rissanen. Modeling by shortest data description.Automatica, 14(5):465–471, 1978

    1978

  15. [23]

    Optimal ordered problem solver.Machine Learning, 54(3):211–254, 2004

    Jürgen Schmidhuber. Optimal ordered problem solver.Machine Learning, 54(3):211–254, 2004

    2004

  16. [24]

    Shifting inductive bias with success-story algorithm, adaptive levin search, and incremental self-improvement.Machine Learning, 28(1):105–130, 1997

    Jürgen Schmidhuber, Jieyu Zhao, and Marco Wiering. Shifting inductive bias with success-story algorithm, adaptive levin search, and incremental self-improvement.Machine Learning, 28(1):105–130, 1997

    1997

  17. [25]

    Estimating the dimension of a model.The Annals of Statistics, 6(2):461–464, 1978

    Gideon Schwarz. Estimating the dimension of a model.The Annals of Statistics, 6(2):461–464, 1978

    1978

  18. [26]

    Uspensky, and Nikolay Vereshchagin.Kolmogorov complexity and algorithmic randomness, volume 220

    Alexander Shen, Vladimir A. Uspensky, and Nikolay Vereshchagin.Kolmogorov complexity and algorithmic randomness, volume 220. American Mathematical Society, 2017

    2017

  19. [27]

    Solomonoff

    Ray J. Solomonoff. A formal theory of inductive inference. Part I.Information and control, 7(1):1–22, 1964

    1964

  20. [28]

    Solomonoff

    Ray J. Solomonoff. A formal theory of inductive inference. Part II.Information and control, 7(2):224–254, 1964

    1964

  21. [29]

    Solomonoff

    Ray J. Solomonoff. Complexity-based induction systems: comparisons and convergence theorems. IEEE transactions on Information Theory, 24(4):422–432, 1978

    1978

  22. [30]

    A decomposition method for global evaluation of Shannon entropy and local estimations of algorithmic complexity.Entropy, 20(8):605, 2018

    Hector Zenil, Santiago Hernández-Orozco, Narsis A Kiani, Fernando Soler-Toscano, Antonio Rueda-Toicen, and Jesper Tegnér. A decomposition method for global evaluation of Shannon entropy and local estimations of algorithmic complexity.Entropy, 20(8):605, 2018. 24

    2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.