Pith. sign in

REVIEW 2 major objections 4 minor 33 references

Text Distance from Nested and Hierarchical Repetitions: A Compression-Based Perspective

T0 review · 2 major / 4 minor · reviewed 2026-07-12 · grok-4.5

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

Pith's one-line read Nested hierarchical repetitions in text yield training-free distances that beat gzip and BERT under distribution shift and few-shot conditions.

desk verdict Solid training-free distances from hierarchical reuse that beat gzip-NCD and BERT on cleaned OOD/few-shot suites; the real lift is L_Dice/L_Jaccard, not the NCD axioms. read the letter →

arxiv 2607.05416 v1 pith:ES5WU7KJ submitted 2026-06-23 cs.CL cs.ITmath.IT

Xiaojun Hu , Jing Wang , Jingwen Zhang , Fengyao Zhai , Xiao Xie , Hao Liao , Zengru Di , Yu Liu This is my paper
classification cs.CLcs.ITmath.IT
keywords AlgorithmicInformationTheoryNormalizedCompressionDistanceLadderpathtextclassificationhierarchicalstructurefew-shotlearningout-of-distribution
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 claims that the nested and hierarchical reuse of repeated substrings is enough to define reliable text distances without any training. The Ladderpath method finds the shortest reconstruction path for a string by treating previously built pieces as reusable building blocks, producing both a compressed length and an explicit hierarchy of those pieces. From that structure the authors define three distances: a Ladderpath-normalized compression distance and two set-like distances analogous to Dice and Jaccard. Paired with a simple nearest-neighbor classifier, all three distances match or exceed gzip-based compression distance on clean in-distribution data and, crucially, outperform both gzip and BERT when the test language or domain shifts and when only a handful of labeled examples are available. The practical payoff is a lightweight, language-agnostic, and fully transparent alternative for sequence comparison whenever annotated data are scarce or distributions are unstable.

What carries the argument

Ladderpath: a reconstruction path that reuses previously recovered substructures (ladderons) to obtain the ladderpath-index λ (shortest path length) and an explicit hierarchy; λ supplies the compressed length for NCD_lp, while the same hierarchy supplies the set sizes for the Dice- and Jaccard-style distances L_Dice and L_Jaccard.

What would settle it

Recompute the same k-NN experiments on the cleaned OOD and 5-shot splits after replacing Ladderpath lengths with any other compressor that fails the normal-compressor checks; if NCD_lp, L_Dice and L_Jaccard no longer beat gzip and BERT, the claim that the hierarchical structure itself is what carries the performance collapses.

Watch

Extended reading notes

Core claim

The nested hierarchical relationships among repeated substructures extracted by Ladderpath preserve intrinsic properties of linguistic sequences that are sufficient for strong training-free text classification; the three distances built from those relationships (NCD_lp, L_Dice, L_Jaccard) consistently outperform both gzip NCD and BERT under out-of-distribution and few-shot regimes.

Load-bearing premise

That the Ladderpath compressor behaves like a normal compressor—so the four required axioms hold within a small error—and that the small length adjustments of −1 and −2 correctly turn λ into a usable compressed length for the distance formulas.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper proposes Ladderpath-based distances for training-free text classification. Ladderpath extracts nested hierarchical repetitions (ladderons) and a ladderpath-index λ as a proxy for compressed length. From this the authors define NCD_lp (with λ′ offsets of −1/−2) and two structure-derived distances L_Dice and L_Jaccard that replace set sizes by individual and joint λ′ values. Combined with k-NN, the three distances are evaluated on cleaned in-distribution, OOD multilingual, and few-shot benchmarks against gzip-NCD, bag-of-words, and BERT. The central empirical claim is that all three Ladderpath distances, and especially L_Dice/L_Jaccard, outperform gzip-NCD and BERT under OOD and low-resource regimes, supporting the view that hierarchical reuse captures intrinsic sequence structure sufficient for classification without training.

Significance. If the OOD and few-shot gains hold under fuller statistical scrutiny, the work supplies a lightweight, language-agnostic, parameter-light alternative to both generic compressors and large pretrained models for low-resource text classification. Strengths that should be credited include: (i) open Ladderpath code, (ii) explicit recomputation of gzip-NCD on de-duplicated data with a fair nearest-neighbor tie-break (Appendix E), (iii) Appendix B checks of normal-compressor axioms, and (iv) k-sensitivity and n-shot curves. The result is of genuine interest to the compression-as-learning and low-resource NLP communities and is not merely a re-packaging of prior gzip-NCD work.

major comments (2)
  1. [Tables 1, 4, 5; Fig. 3; Appendix D] Tables 1, 4 and 5 and Fig. 3 report point accuracies only. No standard errors, bootstrap intervals, or paired significance tests are given, even though DBpedia and SogouNews are subsampled to 10 % (Appendix D / Table 7) without a stated stratification protocol. The OOD/few-shot superiority claim is load-bearing; at minimum the authors should report variability over seeds or stratified folds and confirm that the ranking versus gzip-NCD and BERT remains stable.
  2. [§2.3, equations after (1)] Section 2.3 replaces set cardinalities by λ′(X), λ′(Y) and λ′(X,Y) inside Dice- and Jaccard-style formulae. While the algebraic rewriting is clear, there is no formal argument that λ′ behaves like a measure of set size (monotonicity under inclusion of ladderons, subadditivity, etc.). Because L_Dice and L_Jaccard drive most of the reported gains, a short justification or counter-example analysis would strengthen the claim that these are well-founded structural distances rather than convenient heuristics.
minor comments (4)
  1. [§3.1–3.4] Main experiments use k=7 while Jiang et al. used k=2; appendices supply k=2 tables, but the main text should state the selection criterion more explicitly and note that rankings are stable across the two choices.
  2. [Table 3] Table 3 shows L_Dice and L_Jaccard distances are numerically close but not identical; a one-sentence remark on when the two rankings can diverge would help readers interpret the near-identical accuracies.
  3. [Appendix A] Appendix A compressed_list IDs differ from the main-text example; a brief note that the encoding is order-equivalent would avoid confusion.
  4. [front matter / throughout] A few typographical issues remain (e.g., spacing in title/keywords, occasional missing spaces around math). These do not affect substance.

Circularity Check

1 steps flagged · score 1.0 of 10

No significant circularity: distances are definitional applications of prior Ladderpath work, but OOD/few-shot outperformance claims rest on independent empirical k-NN results against external baselines (gzip, BERT) on public data.

  1. self citation load bearing [§2.1 and citations [18, 19, 25, 26]]
    "The Ladderpath approach, which falls under the umbrella of AIT, seeks to find the shortest path for reconstructing an object... A detailed description of the Ladderpath approach can be found in [18, 25, 26]; only a brief recap is provided here."

    All three distances are built on λ (and the laddergraph) whose definition and minimality claims are imported wholesale from prior papers by overlapping authors (Yu Liu et al.). This is ordinary foundational self-citation, not a reduction of any performance claim to its inputs; the OOD/few-shot accuracies remain independent measurements.

full rationale

The paper's derivation chain defines three distances (NCD_lp via λ' adjustments in §2.2, L_Dice and L_Jaccard via joint-vs-individual λ' in §2.3 after Eq. (1)) directly from the Ladderpath index λ of the authors' prior work, then plugs them into k-NN. This is ordinary method reuse, not a self-definitional loop or fitted-input-as-prediction: no parameter is fit to a data subset and then re-reported as a 'prediction,' no uniqueness theorem is imported to forbid alternatives, and no known empirical pattern is merely renamed. The strongest claims (Tables 1, 4, 5; Figs. 2–3) are classification accuracies measured on cleaned public datasets against gzip-NCD and BERT; those numbers are external empirical facts, not forced by the definitions of λ or the −1/−2 adjustments. Appendix B's normal-compressor checks are likewise empirical (counts of axiom violations across η values) rather than tautological. Self-citations to Ladderpath papers supply the compressor but are not load-bearing for the ranking results. Score 1 only for the minor, non-circular self-citation of the foundational representation; the paper is otherwise self-contained against external benchmarks.

Assumptions & free parameters 3 free parameters · 3 assumptions · 1 invented entities

The paper rests on the pre-existing Ladderpath formalism (λ, ladderons, laddergraph) plus four standard normal-compressor axioms and a handful of implementation choices (k, λ′ offsets, data cleaning). No new physical entities are postulated; free parameters are limited to classifier and encoding knobs.

free parameters (3)
  • k (nearest neighbors) = 7 (main), 2 (ablation)
    Fixed at 7 for main tables (also reported at 2); chosen for near-optimal accuracy rather than derived.
  • λ′ offsets (−1 for single, −2 for pair) = −1 / −2
    Ad-hoc correction ‘to balance taking out the target string(s)’; not forced by the theory.
  • data sampling fraction for DBpedia/SogouNews = ≈10 %
    Approximately 10 % of records retained for compute reasons; selection procedure not fully specified.
assumptions (3)
  • domain assumption Ladderpath index λ equals the length of the shortest hierarchical reconstruction path that reuses previously built substructures (ladderons).
    Taken as given from prior Ladderpath papers; used throughout §2 to define compression length.
  • standard math A compressor satisfying idempotency, monotonicity, symmetry and distributivity (within log n error) yields a valid NCD approximating normalized information distance.
    Standard NCD theory (Li et al., Cilibrasi & Vitanyi); verified empirically for Ladderpath in Appendix B.
  • ad hoc to paper Dice- and Jaccard-style set distances remain meaningful when set sizes are replaced by λ′ values of individual and joint ladderpaths.
    Direct substitution performed in §2.3 without further justification beyond analogy.
invented entities (1)
  • Ladderon / laddergraph representation of a string
    purpose: Encode nested hierarchical repetitions so that reuse can be counted as compression steps.
    Introduced in prior Ladderpath work by overlapping authors; treated as given here. Independent evidence is limited to the same group’s earlier papers and the present empirical classification gains.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Text Distance from Nested and Hierarchical Repetitions: A Compression-Based Perspective." pith.science (2026). https://pith.science/paper/ES5WU7KJ

@misc{pith2026260705416,
  author       = {Pith},
  title        = {Pith review of: Text Distance from Nested and Hierarchical Repetitions: A Compression-Based Perspective},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ES5WU7KJ}},
  note         = {Machine review of arXiv:2607.05416}
}
abstract

We present a new method for structural sequence analysis grounded in Algorithmic Information Theory (AIT). At its core is the Ladderpath approach, which extracts nested and hierarchical relationships among repeated substructures in linguistic sequences -- an instantiation of AIT's principle of describing data through minimal generative programs. These structures are then used to define three distance measures: a normalized compression distance (NCD), and two alternative distances derived directly from the Ladderpath representation. Integrated with a $k$-nearest neighbor classifier, these distances achieve strong and consistent performance across in-distribution, out-of-distribution (OOD), and few-shot text classification tasks. In particular, all three methods outperform both gzip-based NCD and BERT under OOD and low-resource settings. These results demonstrate that the structured representations captured by Ladderpath preserve intrinsic properties of sequences and provide a lightweight, interpretable, and training-free alternative for text modeling. This work highlights the potential of AIT-based approaches for structural and domain-agnostic sequence understanding.

Figures

Figures reproduced from arXiv: 2607.05416 by the authors.

Figure 1
Figure 1. Illustration of nested and hierarchical relationships among repeated substructures in strings, as analyzed using [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Accuracy comparison of k-NN-based methods under varying values of k across different datasets: (a) AGNews dataset; (b) DBpedia dataset; (c) R8 dataset; (d) R52 dataset. In (a), a small portion of the blue LDice line is visible, while the remainder overlaps entirely with the green LJaccard line. In (b), (c), and (d), the blue LDice line is completely obscured due to the overlap with the green line. The reason for thi… view at source ↗
Figure 3
Figure 3. Few-shot performance comparison across multiple datasets. As with Fig. 2, the reason the blue [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Illustration of nested and hierarchical relationships among repeated substructures in strings, as analyzed using [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]
Figure 5
Figure 5. Figure 5: Laddergraph for x and xx. For Monotonicity, it is clear that Idempotency is satisfied when y = 0 or y = x in the presence of C(xy) = C(x). We focus on the casesy ̸= 0 as well as y ̸= x. We can start by going through the construction steps and reuse principles of the La…
Figure 6
Figure 6. Figure 6: Compression method performance by η value: Strong. The horizontal axis represents the orderliness parameter η (0-1), and the vertical axis indicates different compressors. The color intensity reflects the proportion of groups that violate the strong distributive proper…
Figure 7
Figure 7. Figure 7: Impact of split strategies and η values on sequence compression. • Low η: When η is small (0 − 0.2), the overall mean difference fluctuates significantly with the number of truncations. It is hypothesized that when η is small, there are only a limited number of repeate…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

33 extracted references · 4 linked inside Pith

  1. [1]

    Text classification: How machine learning is revolutionizing text categorization.Information, 16, 2025

    Hesham Allam, Lisa Makubvure, Benjamin Gyamfi, Kwadwo Nyarko Graham, and Kehinde Akinwolere. Text classification: How machine learning is revolutionizing text categorization.Information, 16, 2025

    2025

  2. [2]

    A survey on text classification: From traditional to deep learning.ACM Transactions on Intelligent Systems and Technology (TIST), 13(2):1–41, 2022

    Qian Li, Hao Peng, Jianxin Li, Congying Xia, Renyu Yang, Lichao Sun, Philip S Yu, and Lifang He. A survey on text classification: From traditional to deep learning.ACM Transactions on Intelligent Systems and Technology (TIST), 13(2):1–41, 2022. 10

    2022

  3. [3]

    Bert: Pre-training of deep bidirectional transformers for language understanding

    Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. InProceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume 1 (long and short papers), pages 4171–4186, 2019

    2019

  4. [4]

    A survey on few-shot learning in natural language processing

    Mengde Yang. A survey on few-shot learning in natural language processing. In2021 International Conference on Artificial Intelligence and Electromechanical Automation (AIEA), pages 294–297. IEEE, 2021

    2021

  5. [5]

    Low-resource fast text classification based on intra-class and inter-class distance calculation.arXiv preprint arXiv:2412.09922, 2024

    Yanxu Mao, Peipei Liu, Tiehan Cui, Congying Liu, and Datao You. Low-resource fast text classification based on intra-class and inter-class distance calculation.arXiv preprint arXiv:2412.09922, 2024

    arXiv 2024

  6. [6]

    Multi-schema prompting powered token-feature woven attention network for short text classification.Pattern Recognition, 156:110782, 2024

    Zijing Cai, Hua Zhang, Peiqian Zhan, Xiaohui Jia, Yongjian Yan, Xiawen Song, and Bo Xie. Multi-schema prompting powered token-feature woven attention network for short text classification.Pattern Recognition, 156:110782, 2024

    2024

  7. [7]

    Baseline needs more love: On simple word-embedding-based models and associated pooling mechanisms.arXiv preprint arXiv:1805.09843, 2018

    Dinghan Shen, Guoyin Wang, Wenlin Wang, Martin Renqiang Min, Qinliang Su, Yizhe Zhang, Chunyuan Li, Ricardo Henao, and Lawrence Carin. Baseline needs more love: On simple word-embedding-based models and associated pooling mechanisms.arXiv preprint arXiv:1805.09843, 2018

    arXiv 2018

  8. [8]

    Glove: Global vectors for word representation

    Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. InProceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532–1543, 2014

    2014

Show all 33 references
  1. [9]

    Language modeling is compression

    Gregoire Deletang, Anian Ruoss, Paul-Ambroise Duquenne, Elliot Catt, Tim Genewein, Christopher Mattern, Jordi Grau-Moya, Li Kevin Wenliang, Matthew Aitchison, Laurent Orseau, Marcus Hutter, and Joel Veness. Language modeling is compression. InThe Twelfth International Conferen...

    2024

  2. [10]

    Using compression-based language models for text categorization.Language modeling for information retrieval, pages 141–165, 2003

    William J Teahan and David J Harper. Using compression-based language models for text categorization.Language modeling for information retrieval, pages 141–165, 2003

    2003

  3. [11]

    low-resource

    Zhiying Jiang, Matthew Yang, Mikhail Tsirlin, Raphael Tang, Yiqin Dai, and Jimmy Lin. “low-resource” text classification: A parameter-free classification method with compressors. InFindings of the Association for Computational Linguistics: ACL 2023, pages 6810–6828, 2023

    2023

  4. [12]

    An adaptive mutual k-nearest neighbors clustering algorithm based on maximizing mutual information.Pattern Recognition, 137:109273, 2023

    Yizhang Wang, Wei Pang, and Zhixiang Jiao. An adaptive mutual k-nearest neighbors clustering algorithm based on maximizing mutual information.Pattern Recognition, 137:109273, 2023

    2023

  5. [13]

    On tables of random numbers.Sankhy ¯a: The Indian Journal of Statistics, Series A, pages 369–376, 1963

    Andrei N Kolmogorov. On tables of random numbers.Sankhy ¯a: The Indian Journal of Statistics, Series A, pages 369–376, 1963

    1963

  6. [14]

    Bennett, P

    C.H. Bennett, P. Gacs, Ming Li, P.M.B. Vitanyi, and W.H. Zurek. Information distance.IEEE Transactions on Information Theory, 44(4):1407–1423, 1998

    1998

  7. [15]

    Ming Li, Xin Chen, Xin Li, Bin Ma, and P.M.B. Vitanyi. The similarity metric.IEEE Transactions on Information Theory, 50(12):3250–3264, 2004

    2004

  8. [16]

    Cilibrasi and P.M.B

    R. Cilibrasi and P.M.B. Vitanyi. Clustering by compression.IEEE Transactions on Information Theory, 51(4):1523– 1545, 2005

    2005

  9. [17]

    Measurement of text similarity: a survey.Information, 11(9):421, 2020

    Jiapeng Wang and Yihong Dong. Measurement of text similarity: a survey.Information, 11(9):421, 2020

    2020

  10. [18]

    Ladderpath approach: how tinkering and reuse increase complexity and information.Entropy, 24(8):1082, 2022

    Yu Liu, Zengru Di, and Philip Gerlee. Ladderpath approach: how tinkering and reuse increase complexity and information.Entropy, 24(8):1082, 2022

    2022

  11. [19]

    Exploring and mapping chemical space with molecular assembly trees.Science Advances, 7(39):eabj2465, 2021

    Yu Liu, Cole Mathis, Michał Dariusz Bajczyk, Stuart M Marshall, Liam Wilbraham, and Leroy Cronin. Exploring and mapping chemical space with molecular assembly trees.Science Advances, 7(39):eabj2465, 2021

    2021

  12. [20]

    Evolutionary tinkering enriches the hierarchical and nested structures in amino acid sequences

    Zecheng Zhang, Chunxiuzi Liu, Yingjun Zhu, Lu Peng, Weiyi Qiu, Qianyuan Tang, He Liu, Ke Zhang, Zengru Di, and Yu Liu. Evolutionary tinkering enriches the hierarchical and nested structures in amino acid sequences. Physical Review Research, 6(2):023215, 2024

    2024

  13. [21]

    Towards parameter-free data mining

    Eamonn Keogh, Stefano Lonardi, and Chotirat Ann Ratanamahatana. Towards parameter-free data mining. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 206–215, 2004

    2004

  14. [22]

    Evolution and tinkering.Science, 196(4295):1161–1166, 1977

    François Jacob. Evolution and tinkering.Science, 196(4295):1161–1166, 1977

    1977

  15. [23]

    Symmetry and simplicity spontaneously emerge from the algorithmic nature of evolution

    Iain G Johnston, Kamaludin Dingle, Sam F Greenbury, Chico Q Camargo, Jonathan PK Doye, Sebastian E Ahnert, and Ard A Louis. Symmetry and simplicity spontaneously emerge from the algorithmic nature of evolution. Proceedings of the National Academy of Sciences, 119(11):e21138831...

    2022

  16. [24]

    An algorithmic information calculus for causal discovery and reprogramming systems.Iscience, 19:1160–1172, 2019

    Hector Zenil, Narsis A Kiani, Francesco Marabita, Yue Deng, Szabolcs Elias, Angelika Schmidt, Gordon Ball, and Jesper Tegner. An algorithmic information calculus for causal discovery and reprogramming systems.Iscience, 19:1160–1172, 2019

    2019

  17. [25]

    Correlating measures of hierarchical structures in artificial neural networks with their performance.npj Complexity, 1(1):15, 2024

    Zhuoying Xu, Yingjun Zhu, Binbin Hong, Xinlin Wu, Jingwen Zhang, Mufeng Cai, Da Zhou, and Yu Liu. Correlating measures of hierarchical structures in artificial neural networks with their performance.npj Complexity, 1(1):15, 2024

    2024

  18. [26]

    Shu Li, Lu Peng, Liuqing Chen, Linjie Que, Wenqingqing Kang, Xiaojun Hu, Jun Ma, Zengru Di, and Yu Liu. Discovery of highly bioactive peptides through hierarchical structural information and molecular dynamics simulations.Journal of Chemical Information and Modeling, 64(21):81...

    2024

  19. [27]

    Measures of the amount of ecologic association between species.Ecology, 26(3):297–302, 1945

    Lee R Dice. Measures of the amount of ecologic association between species.Ecology, 26(3):297–302, 1945

    1945

  20. [28]

    V-net: Fully convolutional neural networks for volumetric medical image segmentation

    Fausto Milletari, Nassir Navab, and Seyed-Ahmad Ahmadi. V-net: Fully convolutional neural networks for volumetric medical image segmentation. In2016 fourth international conference on 3D vision (3DV), pages 565–571. Ieee, 2016

    2016

  21. [29]

    Dice loss for data-imbalanced nlp tasks.arXiv preprint arXiv:1911.02855, 2019

    Xiaoya Li, Xiaofei Sun, Yuxian Meng, Junjun Liang, Fei Wu, and Jiwei Li. Dice loss for data-imbalanced nlp tasks.arXiv preprint arXiv:1911.02855, 2019

    1911 arXiv

  22. [30]

    Gzip versus bag-of-words for text classification.arXiv preprint arXiv:2307.15002, 2023

    Juri Opitz. Gzip versus bag-of-words for text classification.arXiv preprint arXiv:2307.15002, 2023

    2023 arXiv

  23. [31]

    Guiding prototype networks with label semantics for few-shot text classification.Pattern Recognition, 164:111497, 2025

    Xinyue Liu, Yunlong Gao, Linlin Zong, Wenxin Liang, and Bo Xu. Guiding prototype networks with label semantics for few-shot text classification.Pattern Recognition, 164:111497, 2025

    2025

  24. [32]

    Lossless data compression by large models.Nature Machine Intelligence, pages 1–6, 2025

    Ziguang Li, Chao Huang, Xuliang Wang, Haibo Hu, Cole Wyeth, Dongbo Bu, Quan Yu, Wen Gao, Xingwu Liu, and Ming Li. Lossless data compression by large models.Nature Machine Intelligence, pages 1–6, 2025

    2025

  25. [33]

    ABCDBCDBCDCDEFEF

    Hector Zenil, Narsis A Kiani, Allan A Zea, and Jesper Tegnér. Causal deconvolution by algorithmic generative models.Nature Machine Intelligence, 1(1):58–66, 2019. 12 Appendix A Implementation of Ladderpath-based compressor Figure 4: Illustration of nested and hierarchical rela...

    2019

Pith tools

Reviewed July 12, 2026 · model on record in the stance chip above.