{"id":"97a9af79-fa27-470e-a08d-be214ab85619","arxiv_id":"1908.03781","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Repeatedly extracting shortest features decomposes a string's information into near-independent parts whose total length is within logarithmic error of its Kolmogorov complexity.","lead":"This paper formalizes a way to compress data strings by repeatedly extracting small 'features', so a string is described by a short list of building blocks plus an uncompressible leftover. It proves this step-by-step split can reach near-optimal description length and ties the idea of a feature to randomness tests.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Greedy-ALICE/ALICE do not provably select shortest features: Algorithm 1 enumerates autoencoders by total length l(f')+l(f), so a fast suboptimal feature can be returned and Theorem 3.6's near-optimality is not inherited by the computable algorithm.","rationale":"The reader's weakest assumption identifies the same load-bearing gap I find: the computable algorithms do not realize shortest-feature selection, and no optimality certificate or inherited bound is supplied. I checked the ideal theory and the Martin-Löf correspondence; those proofs appear internally consistent and are stated with appropriate caveats, including Section 4's explicit incomputability concession and Section 6.2's discussion of non-universality. The concern is not that Theorem 3.6 is false; it is that the abstract-level claim of a near-optimal computable incremental compressor outruns the theorems, because ALICE's and Greedy-ALICE's outputs can be arbitrary first successful autoencoders. This does not invalidate the theoretical partition result or the randomness-test connection, so a conditional verdict remains appropriate. The concrete test would settle whether the enumeration order can be patched to preserve near-optimality or whether the paper must be read strictly as an idealized existence theory.","tokens_in":28212,"tokens_out":21799,"duration_ms":250530,"concrete_test":"Construct a finite test instance with a known shortest feature f* of length C and a second autoencoder a_sub=f'_sub f_sub such that l(a_sub)<l(f*)+l(f'*) but l(f_sub)=l(f*)+Delta, both satisfying the compression condition; for example, let f'_sub be a short constant program outputting the empty residual and f_sub a literal printer of x of length Delta above l(f*), chosen so that the total autoencoder length is smaller. Instrument Algorithm 1 to log the first returned (a,f,r) after both autoencoders have halted. If the returned feature is f_sub rather than f*, Greedy-ALICE does not implement shortest-feature selection; repeating with Delta=Theta(l(x)) shows that Theorem 3.6's accuracy claim cannot be transferred without a new proved bound on d. If the algorithm provably always returns l(f)<=l(f*)+O(log l(x)) on such instances, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The conditional core of the paper is Theorem 3.6: if each step selects a shortest feature f_i*, then K(x)=sum_i l(f_i*)+K(r_s)+O(s log l(x)). The computable algorithms in Section 4 do not implement this selection. SearchAutoencoder (Algorithm 1) enumerates a=f'f by total length l(a)=l(f')+l(f) and returns the first autoencoder whose reconstruction y=x satisfies l(f)+l(r)<l(x) inside a dovetailed time budget. Minimal total autoencoder length is not minimal feature length, and the dovetail schedule makes the first return depend on runtime: a long-featured but fast autoencoder (for example, a literal printer of x from the empty residual, with total length just below l(x)) can be returned before the shortest-feature pair, whose descriptive map may need to search an exponentially large residual space. Then d=l(f)-l(f*) in Theorem 3.3 can be large, and the bound in Theorem 3.6 does not transfer to the returned feature. Section 4 itself concedes that shortest features are incomputable, and Theorem 4.1 only bounds the time needed to find some description, never the distance of that description from optimality. Thus the near-optimality claim in the abstract is established only for the ideal non-computable scheme, not for Greedy-ALICE, ALICE, or WILLIAM.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":28486,"tokens_out":16936,"duration_ms":168071,"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":[{"comment":"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.","section":"Section 4.1, Algorithm 1 (SearchAutoencoder), and Theorem 4.1"},{"comment":"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.","section":"Section 3.2, proof of Theorem 3.6"},{"comment":"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.","section":"Abstract, Section 3.6, and Theorem 3.5"}],"minor_comments":[{"comment":"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.","section":"Section 2.2, prefix codes"},{"comment":"In the displayed chain of equalities there is a '> K(y|x)' where an equality or '>=' is intended; please correct this typo.","section":"Lemma 3.4 proof"},{"comment":"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.","section":"Section 4.3"},{"comment":"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.","section":"Algorithm 2"},{"comment":"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'.","section":"Section 6.2"}],"recommendation":"major_revision","confidential_remarks":"The theoretical core of the paper is sound and publishable after revision. The main risk is that the abstract and Section 4 overclaim computable near-optimality; the fix is either a substantial new analysis of the suboptimality penalty d under the actual search order, or a careful restriction of all optimality claims to the ideal shortest-feature scheme. The authors' prior conference paper and WILLIAM work are openly cited, which is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the theory is real, the algorithm is not what the theory promises. The decomposition theorem (Thm 3.6) is a genuine result: if you really can pick a shortest feature at each step, K(x) splits into the feature lengths plus residual complexity up to O(s log l(x)). I went through Theorems 3.1–3.6 and the derivations are honest, based on standard Kolmogorov-complexity identities. The orthogonality bound (Thm 3.5) and the Martin-Löf correspondence (Thms 5.1–5.2) are also new to me and are real contributions. The authors openly say their 2016 conference paper had errors and fix them here; that is the right way to handle prior work.\n\nWhere it gets soft is the bridge to computation. Greedy-ALICE and ALICE search autoencoders by total length l(f')+l(f), not by feature length l(f). The first autoencoder found can have a long feature and a short descriptive map, so it need not be a shortest feature, and the penalty d=l(f)-l(f*) from Thm 3.3 can be large. The paper concedes shortest features are incomputable, and Thm 4.1 only bounds the time to find some description, not how far that description is from optimal. So the near-optimality claim in the abstract is established only for the ideal non-computable scheme, not for ALICE or Greedy-ALICE. The stress-test note is right about this. It is a significant overreach, but it is not a flaw in the theoretical core. I would also want the input-head convention in the proof of Thm 3.6 formalized; it is probably fixable, but as written it is a small gap. The WILLIAM claims in Section 4.3 come with no code or data, so I treat them as anecdotal.\n\nThis paper is for people working on algorithmic information theory and the compression view of features, not for practitioners looking for a usable compressor. It deserves a serious referee. The revision should either restrict the abstract's claims to the ideal scheme or prove that ALICE's returned description is close to optimal (or at least bound l(f)-l(f*)). Without that, the computational half is a heuristic with an inspiring but unproven motivation.","headline":"The theoretical decomposition result is sound and genuinely new; the computable ALICE algorithm does not inherit the near-optimality guarantee, so the abstract overreaches.","tokens_in":29022,"tokens_out":6617,"would_cite":true,"duration_ms":66090,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q30","94A17","03D32"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["incremental compression","Kolmogorov complexity","feature extraction","autoencoder","algorithmic randomness","algorithmic information theory","lossless compression","ALICE"],"falsifier":"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.","tokens_in":27992,"feed_emoji":"🧩","tokens_out":7999,"duration_ms":72801,"temperature":0.7,"pith_summary":"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.'","feed_headline":"Extracting shortest features one by one is near-optimal compression","feed_subtitle":"Incremental feature extraction reaches Kolmogorov complexity up to log overhead, and the search is computable.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the definitions and tools the proofs rest on: prefix Kolmogorov complexity, the symmetry of information, the dovetailed SEARCH procedure, and the algorithmic randomness tests.","marker":"[18]"},{"why":"The earlier conference paper whose core theorems about incremental compression this paper extends and corrects.","marker":"[5]"},{"why":"Introduces stacked autoencoders, the representation that motivates the feature/residual decomposition.","marker":"[8]"},{"why":"Introduces the time-bounded universal search principle that ALICE's dovetailed enumeration generalizes.","marker":"[17]"},{"why":"SS'-Search, the autoencoder-search idea that inspired the feature-search approach used here.","marker":"[21]"},{"why":"Establishes the link between compression and universal intelligence that motivates the practical goal of incremental compression.","marker":"[11]"},{"why":"Proposes the coding theorem method, suggested here as a practical route to search for short features despite incomputability.","marker":"[30]"}],"fun_headline_variants":["Incremental shortest features compress strings near-optimally","Computable incremental compression reaches Kolmogorov bound","Incremental feature search partitions info into incompressible bits","Shortest features iteratively yield near-optimal description length","Incremental compression: near-Kolmogorov via features"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Incremental shortest features compress strings near-optimally","Computable incremental compression reaches Kolmogorov bound","Incremental feature search partitions info into incompressible bits","Shortest features iteratively yield near-optimal description length","Incremental compression: near-Kolmogorov via features"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000989,"raw_usage":{"total_tokens":4165,"prompt_tokens":889,"completion_tokens":3276,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":505,"completion_tokens_details":{"reasoning_tokens":3195}},"tokens_in":505,"tokens_out":3276,"duration_ms":23594,"temperature":1.0,"reasoning_tokens":3195,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:04:59.656035+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Springer, 2009","cited_arxiv_id":null,"evidence_quote":"Supplies the definitions and tools the proofs rest on: prefix Kolmogorov complexity, the symmetry of information, the dovetailed SEARCH procedure, and the algorithmic randomness tests."},{"cited_title":"Some theorems on incremental compression","cited_arxiv_id":null,"evidence_quote":"The earlier conference paper whose core theorems about incremental compression this paper extends and corrects."},{"cited_title":"Hinton and Ruslan R","cited_arxiv_id":null,"evidence_quote":"Introduces stacked autoencoders, the representation that motivates the feature/residual decomposition."},{"cited_title":"Universal sequential search problems.Problemy Peredachi Informatsii, 9(3):115–116, 1973","cited_arxiv_id":null,"evidence_quote":"Introduces the time-bounded universal search principle that ALICE's dovetailed enumeration generalizes."},{"cited_title":"Making universal induction efficient by specialization","cited_arxiv_id":null,"evidence_quote":"SS'-Search, the autoencoder-search idea that inspired the feature-search approach used here."},{"cited_title":"A decomposition method for global evaluation of Shannon entropy and local estimations of algorithmic complexity.Entropy, 20(8):605, 2018","cited_arxiv_id":null,"evidence_quote":"Proposes the coding theorem method, suggested here as a practical route to search for short features despite incomputability."}],"review_version":1}