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

# Text Distance from Nested and Hierarchical Repetitions: A Compression-Based Perspective
Source: [https://arxiv.org/html/2607.05416](https://arxiv.org/html/2607.05416)
Xiaojun Hu1,2,3,11footnotemark:1, Jing Wang1,2,3,11footnotemark:1, Jingwen Zhang1,2, Fengyao Zhai1,2,3, Xiao Xie1,4, Hao Liao5, Zengru Di1,2, Yu Liu1,2,22footnotemark:21Department of Systems Science, Faculty of Arts and Sciences, Beijing Normal University, Zhuhai, China\.2International Academic Center of Complex Systems, Beijing Normal University, Zhuhai, China\.3School of Systems Science, Beijing Normal University, Beijing, China\.4School of Physics and Astronomy, Sun Yat\-sen University, Zhuhai, China\.5College of Computer Science and Software Engineering, Shenzhen University,Shenzhen,China\.

###### 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 akk\-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\.

*K*eywordsAlgorithmic Information Theory \(AIT\)⋅\\cdotNormalized Compression Distance \(NCD\)⋅\\cdotCompression⋅\\cdotLadderpath⋅\\cdotText Classification⋅\\cdotHierarchical Structure

## 1Introduction

The rapid advancements in natural language processing \(NLP\) and machine learning have significantly improved the performance of text classification and regression tasks\[[1](https://arxiv.org/html/2607.05416#bib.bib1),[2](https://arxiv.org/html/2607.05416#bib.bib2)\]\. A wide range of approaches, from traditional bag\-of\-words models to deep neural architectures and pre\-trained language models such as BERT\[[3](https://arxiv.org/html/2607.05416#bib.bib3)\], have been developed to tackle these tasks\. However, deploying these models in low\-resource or distributionally inconsistent scenarios remains a major challenge due to their heavy reliance on extensive annotated data and high computational demands\[[4](https://arxiv.org/html/2607.05416#bib.bib4),[5](https://arxiv.org/html/2607.05416#bib.bib5)\]\. Although these models demonstrate good performance under ideal conditions, their generalization ability often diminishes in settings with scarce data or in the presence of domain shifts\[[6](https://arxiv.org/html/2607.05416#bib.bib6)\]\.

Traditional models and word embedding\-based classifiers require feature engineering or fine\-tuning\[[7](https://arxiv.org/html/2607.05416#bib.bib7),[8](https://arxiv.org/html/2607.05416#bib.bib8)\], while large\-scale models encode a highly compressive mapping of data in an ultra\-high\-dimensional space\. From an information\-theoretic perspective, the process of extracting patterns from data can be viewed as a form of compression—identifying and retaining only the most informative structures\[[9](https://arxiv.org/html/2607.05416#bib.bib9),[10](https://arxiv.org/html/2607.05416#bib.bib10)\]\. Inspired by this insight, Jiang et al\. proposed a parameter\-free classification method that combines a standard compressor \(e\.g\., gzip\) with akk\-nearest neighbor \(kk\-NN\) classifier to approximate deep learning\-like performance without training\[[11](https://arxiv.org/html/2607.05416#bib.bib11),[12](https://arxiv.org/html/2607.05416#bib.bib12)\]\. This method uses thenormalized compression distance\(NCD\) to measure text similarity, offering a lightweight and generalized solution that is especially suited for low\-resource and heterogeneous data\. The theoretical foundation of this approach originates from the concept of information distance and Kolmogorov complexity\[[13](https://arxiv.org/html/2607.05416#bib.bib13)\]\. Bennett et al\. introduced the notion of normalized information distance \(NID\), a universal similarity metric derived from Kolmogorov complexity\[[14](https://arxiv.org/html/2607.05416#bib.bib14)\]\. However, due to the uncomputability of Kolmogorov complexity, NID cannot be directly applied in practice\. To overcome this limitation, Li et al\. proposed using compression algorithms to approximate complexity and introduced NCD, which serves as a computable alternative\[[15](https://arxiv.org/html/2607.05416#bib.bib15)\]\. Cilibrasi and Vitanyi later extended this idea to clustering tasks\[[16](https://arxiv.org/html/2607.05416#bib.bib16)\]\. By estimating the complexity of data objects through compression, NCD provides a model\-free method for distance measurement, supporting training\-free classification frameworks\[[17](https://arxiv.org/html/2607.05416#bib.bib17)\]\.

As mentioned above, compression\-based techniques have demonstrated promising performance in text classification, for example through approaches that combine standard compressor withkk\-NN\[[11](https://arxiv.org/html/2607.05416#bib.bib11)\]\. The appeal of this method lies in its independence from extensive training or prior domain knowledge—it captures intrinsic regularities in data through general\-purpose compression\. However, general\-purpose compressors like gzip are not optimized for semantic or hierarchical textual structures—features commonly found in natural human language—which can constrain their classification accuracy\.

To address these limitations, we propose an alternative compression\-based classification framework based on the Ladderpath approach\[[18](https://arxiv.org/html/2607.05416#bib.bib18),[19](https://arxiv.org/html/2607.05416#bib.bib19)\], which falls under the broader framework of Algorithmic Information Theory \(AIT\)\. Ladderpath performs efficient compression by computing the minimal number of hierarchical reconstruction steps required to reproduce a given string or other data object\[[20](https://arxiv.org/html/2607.05416#bib.bib20)\]\. This allows it to capture nested structural features more effectively than traditional compressors\. Unlike pre\-trained models or parameter\-tuned systems, Ladderpath remains both model\-free and parameter\-free, which significantly enhances its adaptability in dynamic or data\-sparse environments\[[21](https://arxiv.org/html/2607.05416#bib.bib21),[5](https://arxiv.org/html/2607.05416#bib.bib5)\]\. This makes it particularly suitable for real\-world scenarios characterized by low data availability or inconsistent distributions\.

The main contributions of this paper are summarized as follows: \(1\) We propose a new approach grounded in AIT, utilizing the Ladderpath approach to extract the nested and hierarchical relationships among repeated substructures in linguistic sequences and leverage them for compression\. \(2\) We demonstrate that these structured relationships can be used both for compression\-based distance computation—yielding a new normalized compression distance,N​C​Dl​pNCD\_\{lp\}—and for defining distances derived from the Ladderpath representation using ideas analogous to the Dice coefficient and Jaccard index, resulting inLD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}\. \(3\) Experiments show that all three distance measures are effective for text classification tasks\.N​C​Dl​pNCD\_\{lp\}demonstrates performance comparable to the strongest previously reported compression\-based approach, namelyN​C​Dg​z​i​pNCD\_\{gzip\}, whereasLD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}consistently achieve superior performance relative toN​C​Dl​pNCD\_\{lp\}\. Notably, in out\-of\-distribution \(OOD\) and few\-shot settings, all three methods outperform BERT\. This not only provides a practical solution for scenarios with limited labeled data, but more importantly, highlights that the nested and hierarchical relationships extracted by Ladderpath capture intrinsic structural properties of sequences—enabling classification without any training\.

## 2Methods

### 2\.1Recap Ladderpath approach: Capturing nested and hierarchical relationships

The Ladderpath approach, which falls under the umbrella of AIT, seeks to find the shortest path for reconstructing an object \(in this context, a string\), with a key assumption that previously reconstructed substructures can be directly reused in subsequent steps—an idea that echoes François Jacob’s notion of evolutionary tinkering\[[22](https://arxiv.org/html/2607.05416#bib.bib22),[23](https://arxiv.org/html/2607.05416#bib.bib23),[24](https://arxiv.org/html/2607.05416#bib.bib24)\]\. It achieves this goal by identifying repeated substructures and the hierarchical relationships among these substructures\. The length of this shortest path is defined as theladderpath\-indexλ\\lambda\. The hierarchical and nested relationships can be represented as a partially ordered multiset, or equivalently, a directed acyclic graph, referred to as theladdergraph\(see Fig\.[1](https://arxiv.org/html/2607.05416#S2.F1)a and[1](https://arxiv.org/html/2607.05416#S2.F1)b for two examples\)\. A detailed description of the Ladderpath approach can be found in\[[18](https://arxiv.org/html/2607.05416#bib.bib18),[25](https://arxiv.org/html/2607.05416#bib.bib25),[26](https://arxiv.org/html/2607.05416#bib.bib26)\]; only a brief recap is provided here\.

As an illustrative example, consider the string ‘ABCDBCDBCDCDEFEF’\. Its ladderpath is computed using an anonymized implementation \(provided in the Supplementary Material\) and can be represented as a partially ordered multiset:\{\\\{A, B, C, D, E, F // CD, EF // BCD\(2\)\}\\\}\. The corresponding laddergraph is shown in Fig\.[1](https://arxiv.org/html/2607.05416#S2.F1)a\. The ladderpath\-indexλ\\lambdafor this string can also be computed, yielding a value of 10, indicating the minimum number of steps required to reconstruct the target string\.

![Refer to caption](https://arxiv.org/html/2607.05416v1/figures/fig1.png)Figure 1:Illustration of nested and hierarchical relationships among repeated substructures in strings, as analyzed using the Ladderpath approach\. Panels \(a\) and \(c\) display two example strings represented as named Laddergraphs\. Panel \(b\) illustrates the compression process for the string in \(a\), while panel \(d\) shows the corresponding compression for the string in \(c\)\.We can naturally apply the Ladderpath approach to compression because it computes the shortest reconstruction path by algorithmically identifying repeated substructures \(referred to asladderons\) and capturing their nested and hierarchical relationships\. Each ladderon can be encoded in a dictionary with a unique ID, allowing us to simply reference its ID whenever it reappears \(see the Section[2\.2](https://arxiv.org/html/2607.05416#S2.SS2)for a detailed description of the compression procedure\)\.

### 2\.2Ladderpath\-based compressor

Fig\.[1](https://arxiv.org/html/2607.05416#S2.F1)a illustrates the process of compressing a single string using the Ladderpath approach, with the previously discussed string ‘ABCDBCDBCDCDEFEF’ as an example\. After computing its ladderpath, each ladderon is assigned a unique ID: ‘BCD’ receives an ID of 0, ‘CD’ an ID of 1, and ‘EF’ an ID of 2 \(the higher the ID number, the lower the hierarchical level and typically the shorter the ladderon\)\. Referring to Fig\.[1](https://arxiv.org/html/2607.05416#S2.F1)b, starting from the highest ID and moving downward, ‘EF’ comprises the basic building blocks ‘E’ and ‘F’, thus represented directly as \(E,F\)\. Similarly, ‘CD’ consists of the basic building blocks ‘C’ and ‘D’, denoted as \(C,D\)\. The ladderon ‘BCD’ is composed of ‘B’ and ladderon 1 \(namely, ‘CD’\), and is therefore represented as \(B,1\)\. This construction reduces the number of unique symbols: we no longer need to write the full sequence ‘B’, ‘C’, ‘D’, effectively compressing one character\.

Next, for the target string, we assign it a negative ID, here noted as−1\-1, and represent it as \(A,0,0,0,1,2,2\)\. Every time ID 0 appears, we avoid rewriting ‘BCD’, thereby saving two characters per occurrence\. Since ID 0 occurs three times, a total of six characters is saved\. Similarly, each occurrence of ID 1 saves one character, thus two occurrences save two characters, and so forth\. This strategy of eliminating redundant rewrites is the basis of compression in the Ladderpath approach\.

Given the above definitions and constructions, all relevant information can be encoded into a single sequence\. The resulting compression under the Ladderpath framework can be expressed as

z=\(1; A,0,0,0,1,2,2; B,1; C,D; E,F\)z=\\text\{\(1; A,0,0,0,1,2,2; B,1; C,D; E,F\)\}where the first number indicates the total number of target strings—in this case, 1\. The first semicolon\-separated section encodes the target string using ladderon IDs\. The following sections, also separated by semicolons, define all the ladderons: ‘B,1’ corresponds to ladderon ID 0, ‘C,D’ to ID 1, and ‘E,F’ to ID 2\.

Excluding the initial number 1, the total length of this compressed stringzzis 13, which equalsλ\\lambdaplus the total number of ladderons\. In this example,λ\\lambdaequals 10, and there are a total of 3 ladderons\. This can be clearly demonstrated sinceλ\\lambdaitself represents the shortest number of steps required to reconstruct the target string from basic units\. The compressed string directly reflects this minimal reconstruction path\. Note that the number of ladderons \(3 in this case\) is added because combiningnnladderons involves only\(n−1\)\(n\-1\)steps; for example, forming ‘EF’ from ‘E’ and ‘F’ is counted as one step, but in the compressed sequence we must explicitly write two characters, ‘E’ and ‘F’\. Similarly, constructing ‘BCD’ from ‘B’ and ladderon 1 is one step, but we must write both ‘B’ and 1 in the compressed output\. Finally, Fig\.[1](https://arxiv.org/html/2607.05416#S2.F1)b demonstrates the compression of two target strings using the same approach\.

In principle, the sequencezzcan be further compressed into a binary sequence, for example, by using Huffman coding or converting the final compressed sequence into another format \(see Appendix[A](https://arxiv.org/html/2607.05416#A1)for more details\)\. However, such additional steps are not considered here, as the focus is on defining a distance measure and performing text classification based on Ladderpath compression\. In summary, since the ladderpath\-indexλ\\lambdais defined as the length of the shortest reconstruction path derived from the hierarchical and nested relationships among repeated substrings,λ\\lambdacan be used as an effective proxy for the optimally compressed length\.

Finally, according to\[[16](https://arxiv.org/html/2607.05416#bib.bib16)\], to define NCD using a compressor, the compressor should satisfy the following four key properties:Idempotency, ensuring that duplicate data does not affect compression efficiency;Monotonicity, requiring that compressing multiple strings does not yield a smaller result than compressing a single string;Symmetry, indicating that compression results should be independent of the order of input data; andDistributivity, ensuring consistent processing of different string combinations regardless of data structure, order, or chunking method\. A compressor that meets these properties within an acceptable error margin is considered anormal compressor\[[16](https://arxiv.org/html/2607.05416#bib.bib16)\]\. Not all compressors strictly satisfy these four properties\. For instance, widely used compressors such asZ​s​t​a​n​d​a​r​dZstandardexhibit deviations in distributivity\. We have conducted systematic experiments and found that the Ladderpath\-based compressor satisfies these properties within an acceptable error margin \(see Appendix[B](https://arxiv.org/html/2607.05416#A2)for details\)\.

• Normalized Compression Distance \(NCD\): Ladderpath\-based

Once the Ladderpath\-based compressor is shown to function as a normal compressor, it can be used to define a Ladderpath\-based NCD\. When using a compressor, the NCD between two strings,XXandYY, is defined as follows\[[15](https://arxiv.org/html/2607.05416#bib.bib15),[16](https://arxiv.org/html/2607.05416#bib.bib16)\]:

N​C​Dc​\(X,Y\)=c​\(X,Y\)−min⁡\[c​\(X\),c​\(Y\)\]max⁡\[c​\(X\),c​\(Y\)\]NCD\_\{c\}\(X,Y\)=\\frac\{c\(X,Y\)\-\\min\\big\[c\(X\),c\(Y\)\\big\]\}\{\\max\\big\[c\(X\),c\(Y\)\\big\]\}wherec​\(X\)c\(X\)is the length ofXXafter it is compressed using the compressorcc\. By substituting in the Ladderpath\-based compressor, we obtain

N​C​Dl​p​\(X,Y\)=λ′​\(X,Y\)−min⁡\[λ′​\(X\),λ′​\(Y\)\]max⁡\[λ′​\(X\),λ′​\(Y\)\]NCD\_\{lp\}\(X,Y\)=\\frac\{\\lambda^\{\\prime\}\(X,Y\)\-\\min\\big\[\\lambda^\{\\prime\}\(X\),\\lambda^\{\\prime\}\(Y\)\\big\]\}\{\\max\\big\[\\lambda^\{\\prime\}\(X\),\\lambda^\{\\prime\}\(Y\)\\big\]\}whereλ′​\(X\)≡λ​\(X\)−1\\lambda^\{\\prime\}\(X\)\\equiv\\lambda\(X\)\-1andλ′​\(X,Y\)≡λ​\(X,Y\)−2\\lambda^\{\\prime\}\(X,Y\)\\equiv\\lambda\(X,Y\)\-2, andλ\\lambdais the ladderpath\-index\. This small adjustment—subtracting11and22—is applied to balance the operation of taking out the target string\(s\) during reconstruction\. Ifnntargets are taking out, thennnshould be subtracted\. We now applyN​C​Dl​pNCD\_\{lp\}to a text classification task, with results presented in Section[3](https://arxiv.org/html/2607.05416#S3)\.

### 2\.3Define Ladderpath\-distance L

Before conducting the text classification task, two alternative distance measures can be defined directly from the hierarchical and nested relationships among repeated substrings \(i\.e\., ladderons\)\. One of them is based on the idea behind theDice coefficient\. The similarity between two sets,PPandQQ, is defined as the ratio of the size of their intersection to the average size of the two sets, namely\|P∩Q\|/\(\(\|P\|\+\|Q\|\)/2\)\|P\\cap Q\|/\(\(\|P\|\+\|Q\|\)/2\), and consequently, the distance is defined as one minus this similarity\. By applying the inclusion\-exclusion principle, this distance can be derived as:

1−\|P∩Q\|\|P\|\+\|Q\|2=\|P\|\+\|Q\|2−\|P∩Q\|\|P\|\+\|Q\|2=\|P\|\+\|Q\|2−\(\|P\|\+\|Q\|−\|P∪Q\|\)\|P\|\+\|Q\|2=\|P∪Q\|−\|P\|\+\|Q\|2\|P\|\+\|Q\|21\-\\frac\{\|P\\cap Q\|\}\{\\frac\{\|P\|\+\|Q\|\}\{2\}\}=\\frac\{\\frac\{\|P\|\+\|Q\|\}\{2\}\-\|P\\cap Q\|\}\{\\frac\{\|P\|\+\|Q\|\}\{2\}\}=\\frac\{\\frac\{\|P\|\+\|Q\|\}\{2\}\-\(\|P\|\+\|Q\|\-\|P\\cup Q\|\)\}\{\\frac\{\|P\|\+\|Q\|\}\{2\}\}=\\frac\{\|P\\cup Q\|\-\\frac\{\|P\|\+\|Q\|\}\{2\}\}\{\\frac\{\|P\|\+\|Q\|\}\{2\}\}\(1\)
Thus, aLadderpath\-distancebased on the Dice coefficient can be defined as:

LD​i​c​e​\(X,Y\)=λ′​\(X,Y\)−λ′​\(X\)\+λ′​\(Y\)2λ′​\(X\)\+λ′​\(Y\)2L\_\{Dice\}\(X,Y\)=\\frac\{\\lambda^\{\\prime\}\(X,Y\)\-\\frac\{\\lambda^\{\\prime\}\(X\)\+\\lambda^\{\\prime\}\(Y\)\}\{2\}\}\{\\frac\{\\lambda^\{\\prime\}\(X\)\+\\lambda^\{\\prime\}\(Y\)\}\{2\}\}whereλ′​\(X\)\\lambda^\{\\prime\}\(X\)represents the shortest path length required to reconstruct stringXXindividually, corresponding to the set size\|P\|\|P\|in Eq\. \([1](https://arxiv.org/html/2607.05416#S2.E1)\), and similarly forλ′​\(Y\)\\lambda^\{\\prime\}\(Y\)\. Furthermore,λ′​\(X,Y\)\\lambda^\{\\prime\}\(X,Y\)represents the shortest path length when reconstructing stringsXXandYYjointly, corresponding to\|P∪Q\|\|P\\cup Q\|in Eq\. \([1](https://arxiv.org/html/2607.05416#S2.E1)\)\.

Alternatively, the other distance measure is based on the idea behind theJaccard index, in which the similarity between two setsPPandQQis defined as\|P∩Q\|/\|P∪Q\|\|P\\cap Q\|/\|P\\cup Q\|\. The only difference from the Dice coefficient lies in the denominator: the union size rather than the average size\. Following a derivation similar to the one above, aLadderpath\-distancebased on the Jaccard index can be defined as:

LJ​a​c​c​a​r​d​\(X,Y\)=λ′​\(X,Y\)−λ′​\(X\)\+λ′​\(Y\)2λ′​\(X,Y\)2L\_\{Jaccard\}\(X,Y\)=\\frac\{\\lambda^\{\\prime\}\(X,Y\)\-\\frac\{\\lambda^\{\\prime\}\(X\)\+\\lambda^\{\\prime\}\(Y\)\}\{2\}\}\{\\frac\{\\lambda^\{\\prime\}\(X,Y\)\}\{2\}\}Note that both distance measures ensure that whenX=YX=Y, the distance is0, and whenXXandYYshare no common substructure, the distance is11\.

It is worth noting that the similarity or distance measures based on the Jaccard index and the Dice coefficient do exhibit some differences \(although they can be transformed into one another\)\. It is well known that the Jaccard\-based distance satisfies the triangle inequality, making it a true metric\. In contrast, the Dice\-based distance does not satisfy the triangle inequality, and is therefore considered a semimetric version of the Jaccard distance\. Nevertheless, both measures are commonly used in practice\. In some cases, the Dice\-based distance is even preferred because empirical evidence suggests that, compared to the Jaccard index, the Dice coefficient tends to yield higher similarity scores, especially in high\-dimensional, sparse data—such as in bag\-of\-words models or image segmentation masks\. For example, in medical image segmentation \(CT, MRI\), the Dice coefficient is widely used as an evaluation metric\. Similarly, certainnn\-gram–based tasks in natural language processing employ the Dice coefficient\[[27](https://arxiv.org/html/2607.05416#bib.bib27),[28](https://arxiv.org/html/2607.05416#bib.bib28)\]\. In deep learning applications involving medical imaging—such as Mask R\-CNN and other segmentation tasks—Dice loss is extensively used as a loss function \(while Jaccard loss is less common\), due to its smoother gradient properties, which help with network convergence\[[29](https://arxiv.org/html/2607.05416#bib.bib29)\]\. For the sake of completeness, we employ both distance measures in this work to perform text classification tasks\.

## 3Experiments and results

In the work by Jiang et al\.\[[11](https://arxiv.org/html/2607.05416#bib.bib11)\], the authors employedN​C​Dg​z​i​pNCD\_\{gzip\}\(a gzip\-based normalized compression distance\), combined with akk\-NN classifier, to perform text classification across three distinct scenarios: in\-distribution datasets, OOD datasets, and few\-shot learning settings\. They demonstrated that this simple, training\-free approach can achieve performance comparable to—or even surpass—that of large language models such as BERT, despite BERT being a substantially more complex model\.

In this study, we employ the newly defined distances—N​C​Dl​pNCD\_\{lp\}\(Ladderpath\-based normalized compression distance\),LD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}—to carry out classification tasks and compare their performance against the originalN​C​Dg​z​i​pNCD\_\{gzip\}\. The results are presented in the following subsections\.

### 3\.1Experimental setup

All datasets used in this study for text classification are publicly available from their original sources\. A brief description of each dataset is as follows\. AGNews comprises over one million news articles from more than 2,000 sources collected viaComeToMyHead\. DBpedia aggregates structured information from all Wikipedia language editions, Wikidata, Wikimedia Commons, and related projects, and is accessible inTorchText\. R8 and R52 are subsets of the Reuters\-21578 corpus and can be obtained from theText Categorization Corpora\. KinyarwandaNews and KirundiNews consist of news articles from Rwandan and Burundian websites and newspapers and are freely downloadable from thecorresponding repository\. SwahiliNews was specifically created for text classification in the African language Swahili, with each item categorized into six topics, and is freely available throughHuggingFace\. DengueFilipino is a benchmark dataset for low\-resource multiclass classification, primarily in Filipino but containing some English loanwords common in colloquial usage, and is likewise accessible onHuggingFace\. Finally, SogouNews is a large\-scale Chinese corpus provided by Sogou Inc\., comprising extensive text from online news outlets, forums, and blogs, and is publicly distributed viaTorchText\. Detailed download links for all datasets are provided in Appendix[C](https://arxiv.org/html/2607.05416#A3)\.

To ensure high data quality and the reliability of experimental results, we implemented a rigorous data cleaning and screening procedure\. First, we removed duplicate records to retain only unique instances, as duplication can lead thekk\-NN classifier to produce spuriously high performance\. Next, we eliminated contaminated entries—cases in which the same text was associated with inconsistent labels—which would otherwise introduce noise and increase the risk of misclassification\. Furthermore, for the large\-scale DBpedia and SogouNews datasets, we selected approximately 10% of the available records for our experiments \(see Appendix[D](https://arxiv.org/html/2607.05416#A4)for details\)\. This sampling strategy preserved the representativeness of the data while substantially reducing computational time and cost\.

### 3\.2For in\-distribution datasets

Now, we conduct classification experiments using the newly defined distances, and the results are presented in Table[1](https://arxiv.org/html/2607.05416#S3.T1)\. For comparison, we adopt the accuracy values for TextCNN, LSTM, W2V, and BERT from the work by Jiang et al\.\[[11](https://arxiv.org/html/2607.05416#bib.bib11)\], and use TextLength \(i\.e\., classifying based on text length\) as the baseline\. It is important to note that the accuracy ofN​C​Dg​z​i​pNCD\_\{gzip\}reported in\[[11](https://arxiv.org/html/2607.05416#bib.bib11)\]was slightly inflated\[[30](https://arxiv.org/html/2607.05416#bib.bib30)\], due to the use of an uncleaned dataset and an optimistic tie\-breaking strategy in thekk\-NN classifier \(see Appendix[E](https://arxiv.org/html/2607.05416#A5)for details\)\. In fact, the authors later acknowledged this issue\. Consequently, we recomputed the classification accuracy forN​C​Dg​z​i​pNCD\_\{gzip\}using the same methodology but on the cleaned dataset\.

Table 1:Comparison results on text classification datasets\.As shown in Table[1](https://arxiv.org/html/2607.05416#S3.T1), we report the results for the three newly defined distance measures:N​C​Dl​pNCD\_\{lp\},LD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}\. Among methods that do not rely on pre\-training or task\-specific training,LD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}attain the highest classification accuracies;N​C​Dl​pNCD\_\{lp\}outperformsN​C​Dg​z​i​pNCD\_\{gzip\}in most cases\. These results indicate that the proposed measures exhibit competitive classification performance, suggesting that the hierarchical and nested structures captured by Ladderpath approach can provide meaningful similarity representations for text classification tasks\. Note that in our experiments, we set the parameterk=7k=7for allkk\-NN\-based methods, rather than usingk=2k=2as in the study by Jiang et al\., sincek=7k=7consistently yields near\-optimal performance across these methods\. For completeness, however, we also report the results withk=2k=2in Table[2](https://arxiv.org/html/2607.05416#S3.T2), whereLD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}likewise achieve the best performance\.

Table 2:Classification results under the same setting as Table[1](https://arxiv.org/html/2607.05416#S3.T1), but withk=2k=2, following the settings in Jiang et al\. Some of the results reported in their study appear higher than ours because, as explained in Appendix[E](https://arxiv.org/html/2607.05416#A5), theirkk\-NN classification systematically adopted the most optimistic scenario\. Jiang et al\. have since acknowledged this issue and updated certain results on their GitHub repository\.In Table[1](https://arxiv.org/html/2607.05416#S3.T1), we also presented the results of thebag\-of\-wordsapproach, as described in\[[30](https://arxiv.org/html/2607.05416#bib.bib30)\]\. This method represents a conventional text classification technique that relies on word occurrence patterns rather than deep contextual understanding or direct distance\-based comparison\. Specifically, it follows a three\-step preprocessing pipeline: \(1\) removing punctuation and replacing it with spaces; \(2\) filtering out words below a certain frequency threshold; and \(3\) converting all uppercase letters to lowercase\. After this transformation, texts are represented as independent word vectors, which are then used to compute similarities and perform classification\. Notably, we observe that this approach also yields strong performance in classification tasks\. However, it is important to emphasize that its success primarily stems from an inherent form of semantic segmentation, in which words naturally serve as meaningful semantic units\. In contrast, compression\-based and Ladderpath\-based methods operate without incorporating any prior semantic knowledge\.

Note that in Table[1](https://arxiv.org/html/2607.05416#S3.T1)and[2](https://arxiv.org/html/2607.05416#S3.T2), we observe nearly identical classification accuracies forLD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}, which may appear somewhat unexpected\. Nevertheless, this outcome can be clarified through a closer examination of their empirical behavior\. Specifically, we compared the distance matrices between one focal text and ten reference texts within the AGNews dataset, as presented in Table[3](https://arxiv.org/html/2607.05416#S3.T3)\. The analysis reveals that, for the same text pairs, the distance values produced byLD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}are numerically very close, though not strictly identical\. These marginal discrepancies exert only a negligible effect on the performance of thekk\-NN classifier\. Consequently, despite their theoretical distinctions,LD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}yield highly consistent assessments of text similarity in practice, which accounts for the near\-equivalence observed in their classification accuracies\.

Table 3:Comparison of pairwise distances between a focal training text and multiple test texts in the AGNews dataset, evaluated usingLD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}\.Finally, we report the classification accuracies obtained for different values ofkkin Fig\.[2](https://arxiv.org/html/2607.05416#S3.F2)\. The results reveal that \(1\) the Ladderpath\-compression\-based distanceN​C​Dl​pNCD\_\{lp\}surpassesN​C​Dg​z​i​pNCD\_\{gzip\}on DBpedia and R52, performs comparably on AGNews, and is outperformed byN​C​Dg​z​i​pNCD\_\{gzip\}only on R8; \(2\) the Ladderpath\-distanceLD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}achieve the best performance across all four datasets—except that on R8,N​C​Dg​z​i​pNCD\_\{gzip\}remains similarly strong\.

![Refer to caption](https://arxiv.org/html/2607.05416v1/figures/fig2.png)Figure 2:Accuracy comparison ofkk\-NN\-based methods under varying values ofkkacross different datasets: \(a\) AGNews dataset; \(b\) DBpedia dataset; \(c\) R8 dataset; \(d\) R52 dataset\. In \(a\), a small portion of the blueLD​i​c​eL\_\{Dice\}line is visible, while the remainder overlaps entirely with the greenLJ​a​c​c​a​r​dL\_\{Jaccard\}line\. In \(b\), \(c\), and \(d\), the blueLD​i​c​eL\_\{Dice\}line is completely obscured due to the overlap with the green line\. The reason for this behavior has been discussed above\.
### 3\.3For out\-of\-distribution \(OOD\) datasets

OOD robustness is a major challenge for modern machine learning systems, which must maintain reliable performance when test data differ substantially from the training distribution\. Compression\-based and Ladderpath\-based methods are particularly well suited to this setting because they require no pre\-training or language\-specific fine\-tuning\.

We evaluated OOD robustness on five datasets in different natural languages—Kinyarwanda, Kirundi, Filipino, Swahili, and Chinese \(SogouNews\)—as listed in Table[4](https://arxiv.org/html/2607.05416#S3.T4)\. BERT serves as a baseline, with its accuracy taken from Jiang et al\.\[[11](https://arxiv.org/html/2607.05416#bib.bib11)\]\. Among purely distance\-based approaches,LD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}consistently outperformN​C​Dg​z​i​pNCD\_\{gzip\}, whileN​C​Dl​pNCD\_\{lp\}andN​C​Dg​z​i​pNCD\_\{gzip\}exhibit comparable accuracy, each surpassing the other in roughly half of the tasks\. It should be noted that, for reasons discussed earlier, the accuracy values ofN​C​Dg​z​i​pNCD\_\{gzip\}originally reported by Jiang et al\.\[[11](https://arxiv.org/html/2607.05416#bib.bib11)\]were slightly inflated\[[30](https://arxiv.org/html/2607.05416#bib.bib30)\]\. The authors have acknowledged this issue and released corrected results in subsequent GitHub comments \(link is provided in Appendix[C](https://arxiv.org/html/2607.05416#A3)\), which we adopt for a fair comparison\.

Table 4:Comparison of text classification accuracy across various methods and OOD datasets\. Among the four distance\-based methods below, the highest accuracy in each row is highlighted in bold\. If BERT’s accuracy exceeds the best of the four distance\-based methods, it is additionally marked with an underline\. Allkk\-NN\-based methods usek=7k=7, in contrast to Jiang et al\.’s study, which usedk=2k=2\. For reference, the results withk=2k=2are provided in Appendix[F](https://arxiv.org/html/2607.05416#A6)\.An important implication of these results is the cross\-lingual generality of the Ladderpath approach\. Despite having no prior linguistic knowledge of these diverse languages, the Ladderpath\-derived distances capture structural regularities that align closely with semantic similarity\. In other words, the hierarchical and nested patterns detected by Ladderpath provide a language\-agnostic metric of textual relatedness\. This explains whyLD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}achieve strong and stable performance across typologically different languages without any additional adaptation\.

### 3\.4Few\-shot setting

Few\-shot classification tasks pose a significant challenge for conventional machine learning models, particularly when the number of labeled examples per class is extremely limited or when the label distribution is highly imbalanced\[[31](https://arxiv.org/html/2607.05416#bib.bib31)\]\. While many recent few\-shot methods rely on large pre\-trained models or meta\-learning frameworks, we explore a fundamentally different direction based on compression\-based and training\-free approaches\. These methods, includingN​C​Dl​pNCD\_\{lp\},LD​i​c​eL\_\{Dice\}, andLJ​a​c​c​a​r​dL\_\{Jaccard\}, are naturally suited to low\-resource and OOD scenarios\.

To evaluate the effectiveness of different compression\-based distance metrics in such low\-resource conditions, we conduct experiments on five OOD datasets using the 5\-shot setting\. The results, presented in Table[5](https://arxiv.org/html/2607.05416#S3.T5), show that: \(1\) the traditional compression\-based methodN​C​Dg​z​i​pNCD\_\{gzip\}outperforms BERT on 3 out of the 5 datasets and performs comparably to the Ladderpath\-based compression methodN​C​Dl​pNCD\_\{lp\}; \(2\) the distance measures computed directly from Ladderpath, namelyLD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}, significantly outperform both BERT andN​C​Dg​z​i​pNCD\_\{gzip\}\. These findings suggest that pre\-training\-free methods—especially those based on our Ladderpath approach, which captures the nested and hierarchical relationships among repeated substructures—are better equipped to extract discriminative features from limited samples\.

Table 5:Comparison of text classification accuracy across various methods on OOD datasets under the 5\-shot setting\. Among the four distance\-based methods below, the highest accuracy in each row is highlighted in bold\. Allkk\-NN\-based methods usek=7k=7, in contrast to Jiang et al\.’s work, which usedk=2k=2\. For reference, results withk=2k=2are provided in Appendix[G](https://arxiv.org/html/2607.05416#A7)\.Beyond OOD tasks, few\-shot learning is also applicable to in\-distribution scenarios, particularly when aiming for lightweight models or when annotation costs are high\. To further evaluate the scalability and robustness of the proposed distance measures, we carried out additional experiments under differentnn\-shot settings \(n∈\{5,10,50,100\}n\\in\\\{5,10,50,100\\\}\) on three datasets: AGNews, DBpedia, and SogouNews\. The results, shown in Fig\.[3](https://arxiv.org/html/2607.05416#S3.F3), indicate that the Ladderpath\-based distancesLD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}markedly outperform all other methods across all tested cases\. These results complement the OOD evaluation in Table[5](https://arxiv.org/html/2607.05416#S3.T5)by illustrating performance trends as the number of labeled examples increases\. We selected these three datasets because their data scales are sufficiently large to support 100\-shot experiments, and they differ in average text length and language\. This diversity enables a more comprehensive evaluation across heterogeneous input conditions while ensuring consistency across varying few\-shot levels\.

![Refer to caption](https://arxiv.org/html/2607.05416v1/figures/fig3.png)Figure 3:Few\-shot performance comparison across multiple datasets\. As with Fig\.[2](https://arxiv.org/html/2607.05416#S3.F2), the reason the blueLD​i​c​eL\_\{Dice\}line is not visible is that it is completely obscured by the overlapping greenLJ​a​c​c​a​r​dL\_\{Jaccard\}line\.Taken together, the few\-shot results show that Ladderpath\-derived distances are particularly effective under scarce supervision, consistently outperforming both neural and traditional compression\-based baselines across OOD and in\-distribution settings\. This advantage remains stable as the number of labeled examples increases, indicating strong scalability in low\-resource regimes\. More importantly, these findings suggest that explicitly modeling hierarchical reuse yields representations that are inherently sample\-efficient: rather than relying on parameter learning, this approach exploits structural regularities in the data itself, making it well suited for few\-shot and low\-resource sequence understanding\.

## 4Discussion

The effectiveness of text classification fundamentally depends on both the quality of feature extraction and the suitability of the classification model\. Deep learning architectures—such as convolutional neural networks and pre\-trained language models like BERT—have achieved remarkable success by capturing deep semantic patterns in text\. However, these methods typically require large\-scale annotated datasets, substantial computational resources, and often struggle with generalization under domain shift or low\-resource conditions\.

In contrast, the Ladderpath approach offers a lightweight, training\-free alternative grounded in AIT\. By directly identifying repeated substructures and capturing their nested and hierarchical relationships, Ladderpath constructs a structural representation that is both compact and informative\. These relationships are then leveraged to define distance measures—either through compression\-based comparison \(yieldingN​C​Dl​pNCD\_\{lp\}\) or via structure\-inspired metrics \(LD​i​c​eL\_\{Dice\},LJ​a​c​c​a​r​dL\_\{Jaccard\}\)—and combined with a simplekk\-NN classifier\. Our empirical results demonstrate that these Ladderpath\-based distances consistently achieve strong classification performance, often comparable to deep learning baselines\. In particular,LD​i​c​eL\_\{Dice\}andLJ​a​c​c​a​r​dL\_\{Jaccard\}outperform traditional gzip\-based NCD in both OOD and few\-shot settings, highlighting the expressiveness and robustness of the hierarchical structure captured by Ladderpath\.

From a methodological perspective, the strength of the Ladderpath approach lies in the nature of its inductive bias\. Rather than learning representations through gradient\-based optimization, it enforces a structural bias toward reuse and minimal generative description\. This bias favors representations that are inherently sample\-efficient, as they are derived directly from the internal organization of the data rather than from statistical estimation over large corpora\. As a result, Ladderpath\-based distances remain stable under limited supervision and distribution shift, where learned representations often struggle\.

This distinction is further reflected in our comparison with bag\-of\-words\-based approaches, which typically involve aggressive preprocessing steps such as lowercasing, punctuation removal, and filtering of short or infrequent words\. These procedures, while not explicitly semantic, introduce strong linguistic priors that help segment the input into semantically meaningful units\. In contrast, Ladderpath retains the raw sequential order of the text while structurally compressing it based on internal repetition and recursive reuse\. As such, it captures meaningful regularities in a domain\-agnostic and language\-independent manner—providing a structural and interpretable perspective on text compression and similarity\.

Taken together, these observations position Ladderpath as a complementary alternative to model\-centric approaches in text classification\. By focusing on structural compression rather than parameter learning, it highlights a different axis of generalization—one grounded in reusable structure rather than learned semantics—which may be particularly valuable in transparent, low\-resource, or cross\-lingual settings\.

## 5Conclusion

In this work, we leveraged the Ladderpath approach as a structural representation grounded in AIT to define a family of distance measures for text classification\. By operating directly on Ladderpath\-derived structures rather than learned parameters, these distances achieve strong and stable performance across in\-distribution, out\-of\-distribution, and few\-shot settings, demonstrating their effectiveness for sequence comparison when labeled data are limited\.

Beyond classification, the Ladderpath approach provides a general perspective on sequence modeling that emphasizes minimal generative structure rather than parameter learning\. By preserving nested and hierarchical relationships among repeated substructures, it supports structure\-aware similarity estimation and may serve as a preprocessing or tokenization module for downstream models\. More broadly, the core principles underlying Ladderpath—recursive structure reuse and information\-theoretic minimality—resonate with a growing line of work that views compression as a key organizing principle for representation learning and intelligence\[[9](https://arxiv.org/html/2607.05416#bib.bib9),[32](https://arxiv.org/html/2607.05416#bib.bib32),[33](https://arxiv.org/html/2607.05416#bib.bib33)\]\. Together, these results highlight the value of structurally grounded, compression\-based representations for robust sequence understanding under data scarcity and distribution shift\.

## 6Acknowledgment

We gratefully acknowledge Prof\. Fan Jin and Prof\. Ziwei Dai for their insightful suggestions and constructive discussions\. This study was funded by the National Natural Science Foundation of China \(Grant No\. 12205012 to Y\.L\.\) and Basic and Applied Basic Research Foundation of Guangdong Province \(Grant No\. 2025A1515012923 to Y\.L\.\)\.

## 7Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper\.

## 8Data availability

## References

- \[1\]Hesham Allam, Lisa Makubvure, Benjamin Gyamfi, Kwadwo Nyarko Graham, and Kehinde Akinwolere\.Text classification: How machine learning is revolutionizing text categorization\.Information, 16, 2025\.
- \[2\]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\.
- \[3\]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\.
- \[4\]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\.
- \[5\]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\.
- \[6\]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\.
- \[7\]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\.
- \[8\]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\.
- \[9\]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 Conference on Learning Representations, 2024\.
- \[10\]William J Teahan and David J Harper\.Using compression\-based language models for text categorization\.Language modeling for information retrieval, pages 141–165, 2003\.
- \[11\]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\.
- \[12\]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\.
- \[13\]Andrei N Kolmogorov\.On tables of random numbers\.Sankhyā: The Indian Journal of Statistics, Series A, pages 369–376, 1963\.
- \[14\]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\.
- \[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\.
- \[16\]R\. Cilibrasi and P\.M\.B\. Vitanyi\.Clustering by compression\.IEEE Transactions on Information Theory, 51\(4\):1523–1545, 2005\.
- \[17\]Jiapeng Wang and Yihong Dong\.Measurement of text similarity: a survey\.Information, 11\(9\):421, 2020\.
- \[18\]Yu Liu, Zengru Di, and Philip Gerlee\.Ladderpath approach: how tinkering and reuse increase complexity and information\.Entropy, 24\(8\):1082, 2022\.
- \[19\]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\.
- \[20\]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\.
- \[21\]Eamonn Keogh, Stefano Lonardi, and Chotirat Ann Ratanamahatana\.Towards parameter\-free data mining\.InProceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 206–215, 2004\.
- \[22\]François Jacob\.Evolution and tinkering\.Science, 196\(4295\):1161–1166, 1977\.
- \[23\]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\):e2113883119, 2022\.
- \[24\]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\.
- \[25\]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\.
- \[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\):8164–8175, 2024\.
- \[27\]Lee R Dice\.Measures of the amount of ecologic association between species\.Ecology, 26\(3\):297–302, 1945\.
- \[28\]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\.
- \[29\]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\.
- \[30\]Juri Opitz\.Gzip versus bag\-of\-words for text classification\.arXiv preprint arXiv:2307\.15002, 2023\.
- \[31\]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\.
- \[32\]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\.
- \[33\]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\.

## Appendix

## Appendix AImplementation of Ladderpath\-based compressor

![Refer to caption](https://arxiv.org/html/2607.05416v1/figures/figS1.png)Figure 4:Illustration of nested and hierarchical relationships among repeated substructures in strings, as analyzed using the Ladderpath approach\.Still taking the string “ABCDBCDBCDCDEFEF” as an example \(Fig\.[1](https://arxiv.org/html/2607.05416#S2.F1)a in the main text\), after processing with the Ladderpath approach, we obtain three ladderons as Fig\.[4](https://arxiv.org/html/2607.05416#A1.F4)shows\. The original string is essentially composed of basic buildings and these ladderons\.

At the operational level, we can compute it using the code we provide as follows:

`We can see that the result is not exactly the same as the one shown in the original text, z=\(1;A,0,0,0,1,2,2;B,1;C,D;E,F\)z=\(1;A,0,0,0,1,2,2;B,1;\\allowbreak C,D;E,F\),but they correspond one\-to\-one\. Let’s now explain the structure of the above ‘compressed\_list’: ‘@’ serves as a delimiter to separate different sequences and ladderons\. The first element, ‘1’, indicates that the target sequence contains only one string\. The subsequent elements describe the reconstruction process of the original string, where “‘A’, 2, 2, 2, 1, 0, 0” means that the basic building block ‘A’ is first combined with element 2 \(explained below\), then again with element 2, followed in turn by element 2, element 1, element 0, and element 0, until the full string is recovered\. Next, three ‘@’ symbols separate three elements\. The first pair ‘@’, ‘EF’, designates element 0, meaning element 0 is created by combining the basic building blocks ‘E’ and ‘F’\. The second pair, ‘@’, ‘CD’, designates element 1, formed by combining the basic building blocks ‘C’ and ‘D’\. The third group, ‘@’, ‘B’, 1, designates element 2, which is constructed from the basic building block ‘B’ and element 1\. Note that the IDs shown in the ‘compressed\_list’ can differ from those assigned by the Ladderpath algorithm itself, owing to implementation details\. This design is primarily motivated by operational considerations, making subsequent processing more convenient\. For instance, the inclusion of explicit separators \(such as ‘@’\) in the compressed list facilitates structural parsing and reconstruction\. Moreover, this list can be directly used as input for entropy encoding methods–such as Huffman coding—to achieve further compression and efficient storage\.`

`Appendix B Normal compressor First, the concept of η\\eta is briefly recapped, as it will be needed later\. In the Ladderpath approach, there are three primary indices for measuring a system: • Ladderpath\-index \(λ\\lambda\): The length of the shortest ladderpath for a target\. • Size\-index \(SS\): The length of the shortest trivial ladderpath for an object\. • Order\-index \(ω\\omega\): Defined as ω​\(x\):=S​\(x\)−λ​\(x\)\\omega\(x\):=S\(x\)\-\\lambda\(x\), this means that the work has been saved from combining blocks when constructing the target\. Based on these definitions, the η\\eta is calculated by the following formula: η=ω​\(x\)−ω0​\(S\)ωmax​\(S\)−ω0​\(S\)\\eta=\\frac\{\\omega\(x\)\-\\omega\_\{0\}\(S\)\}\{\\omega\_\{\\text\{max\}\}\(S\)\-\\omega\_\{0\}\(S\)\} where ω0​\(S\)\\omega\_\{0\}\(S\) represents the average Order\-index of all possible sequences of length SS\. ωmax​\(S\)\\omega\_\{\\text\{max\}\}\(S\) represents the maximum Order\-index among all sequences of length SS\. Through the aforementioned formula, η\\eta is used to quantify the degree of orderliness of a sequence, reflecting the structural characteristics of the system at a specific length SS \(details can be referred to reference Zhang et al\., Physical Review Research 6\(2\):023215, 2024\)\. Then, we explain “Normal Compressor”\. A compressor that can satisfy these four properties with an error range of log⁡\(n\)\\log\(n\) is called a “Normal Compressor” \(Li et al\., IEEE Transactions on Information Theory 50\(12\):3250–3264, 2004\)\. • Idempotency: C​\(x​x\)=C​\(x\)​ and ​C​\(A\)=0, when ​A=∅\.C\(xx\)=C\(x\)\\text\{~and~\}C\(A\)=0,\\\\ \\text\{~when~\}A=\\emptyset\. • Monotonicity: C​\(x​y\)≥C​\(x\)\.C\(xy\)\\geq C\(x\)\. • Symmetry: C​\(x​y\)=C​\(y​x\)\.C\(xy\)=C\(yx\)\. • Distributivity: C​\(x​y\)\+C​\(z\)≤C​\(x​z\)\+C​\(y​z\)\.C\(xy\)\+C\(z\)\\leq C\(xz\)\+C\(yz\)\. For Idempotency, with x=A​B​C​D​E​F​B​C​Dx=ABCDEFBCD, C​\(x\)=λx−1=6C\(x\)=\\lambda\_\{x\}\-1=6, C​\(x​x\)=λx​x−2=6C\(xx\)=\\lambda\_\{xx\}\-2=6\. Combined with the reuse principle of Ladderpath, it is clear that after constructing the subsequence xx, it can be reused infinitely many times without consuming additional resources without consuming additional resources\. In the process of combining x​xxx, we need to take out the sequence xx twice, and this operation has nothing to do with the compression process, so we have C​\(x​x\)=λx​x−2C\(xx\)=\\lambda\_\{xx\}\-2\. Figure 5: Laddergraph for xx and x​xxx\. For Monotonicity, it is clear that Idempotency is satisfied when y=0y=0 or y=xy=x in the presence of C​\(x​y\)=C​\(x\)C\(xy\)=C\(x\)\. We focus on the casesy≠0y\\neq 0 as well as y≠xy\\neq x\. We can start by going through the construction steps and reuse principles of the Ladderpath\. The construction of the string x​yxy must contain the steps necessary to construct xx; thus, its cost is at least equal to the cost of constructing xx\. Specifically, the minimum number of steps to construct x​yxy: λx​y≥λx\\lambda\_\{xy\}\\geq\\lambda\_\{x\}, and the savings from reuse do not affect this inequality, so we can know that: C​\(x​y\)≥C​\(x\)C\(xy\)\\geq C\(x\)\. Even if yy introduces a new structure, its steps do not reduce the overhead of the xx part, thus ensuring that Monotonicity holds\. Symmetry is the same as Idempotency\. The Ladderpath compressor tends to generate xx and yy first when compressing objects x​yxy and y​xyx, so the difference between generating x​yxy and y​xyx is whether to take out xx or yy first, which is only the last step, and the resources for compressing xx and yy in the previous step are unchanged\. For the fourth Distributivity, there is a stronger distributive law C​\(x​y​z\)\+C​\(z\)<C​\(x​z\)\+C​\(y​z\)C\(xyz\)\+C\(z\)<C\(xz\)\+C\(yz\), and here we continue the idea of NCD and use a slightly weaker distributive law for verification \(subsequently referred to as “weak”\)\. Firstly, it should be noted that in the experimental design, in order to encompass as much as possible the various possibilities from purely random sequences to fully homogeneous sequences and to eliminate the influence of the number of repeated substructures within the sequence on the compression efficiency\. We chose η=\[0,0\.1,0\.2,…,0\.95\]\\eta=\[0,0\.1,0\.2,\.\.\.,0\.95\], each containing 100 strings\. In Table 6, we compare the different compressors that do not satisfy the distributivity for each data group under the strong and weak constraints, respectively\. Table 6: Counts of violations under different η\\eta values for various compression methods\. Across different η\\eta values, nearly all compression methods satisfy the weakly relaxed distributivity of Kolmogorov complexity within the acceptable margin of error\. Ladderpath demonstrates relatively greater stability, with only two string sequences failing to meet the weak distributivity\. In contrast, gzip exhibits three violations, while Zstandard performs the worst, with eight sequences not conforming to the property\. Under the strong constraints of Kolmogorov complexity, Ladderpath’s anomalous values remain in an intermediate state\. Gzip shows the poorest performance, particularly when compressing disordered sequences with smaller η\\eta values, where a substantial number of instances fail to satisfy the strong distributivity\. Regardless of the chosen η\\eta\-value, LZ77 consistently achieves the best performance\. Figure 6: Compression method performance by η\\eta value: Strong\. The horizontal axis represents the orderliness parameter η\\eta \(0\-1\), and the vertical axis indicates different compressors\. The color intensity reflects the proportion of groups that violate the strong distributive property\. Darker colors \(towards red\) indicate poorer performance, while lighter colors \(towards white\) indicate better performance\. To be more comprehensive, we conducted additional tests to examine the satisfaction of “strong” distributivity—the most challenging property to satisfy—namely, C​\(x​y\)\+C​\(z\)≤C​\(x​z\)\+C​\(y​z\)C\(xy\)\+C\(z\)\\leq C\(xz\)\+C\(yz\), as shown in Fig\. 6\. The results show that none of the tested compression algorithm can strictly satisfy the strong distributivity, with g​z​i​pgzip and b​z​i​p​2bzip2 showing significant outliers and large deviations\. Ladderpath\-based compressor almost completely satisfies the strong distributivity for small η\\eta \(e\.g\., less than 0\.4\)\. It almost always satisfies the strong distributivity, while typically, natural language texts have an ordering rate η\\eta in this range\. For strong distributivity, the better the satisfaction, the more effective their discriminative distances are\. In summary, the Ladderpath\-based compressor shows good properties compared to some other compressors, and outperforms traditional compressors such as g​z​i​pgzip and Z​s​t​a​n​d​a​r​dZstandard\. Appendix C Download datasets Detailed download links for all datasets are listed below: • • • • • • • • Appendix D Data preprocessing Table 7 presents the sizes of all datasets\. Table 7: Original data volume and the data volume used in our experiments\. In addition, note that some datasets contain sentences of considerable length\. To reduce computational cost—since the runtime of the Ladderpath approach grows with sentence length—we divided such long sentences into shorter segments\. An important question, however, is whether splitting a long sentence into multiple shorter segments affects the resulting Ladderpath measure\. To examine this, we conducted the following test\. For each sentence, we randomly introduced from 1 to 50 cuts: one cut yields two shorter segments, two cuts yield three segments, and so on, up to 50 cuts yielding 51 segments\. We then applied the Ladderpath compression independently to each truncated segment and compared the aggregate results with those obtained from the original unsplit sentence\. The zz\-axis of Fig\. 7 reports the average difference between the computed values\. The parameter η\\eta was varied over the range \[0,0\.1,0\.2,…,0\.95\]\[0,0\.1,0\.2,\\ldots,0\.95\], and for each η\\eta we analyzed 10 randomly generated strings\. Figure 7: Impact of split strategies and η\\eta values on sequence compression\. Combined with the results in Fig\. 7, the following conclusions can be drawn: • Low η\\eta: When η\\eta is small \(0−0\.20\-0\.2\), the overall mean difference fluctuates significantly with the number of truncations\. It is hypothesized that when η\\eta is small, there are only a limited number of repeated fragments available\. The truncation operation may further disrupt the redundant repetitions that could be utilized by Ladderpath, leading to a significant response in the truncated compression difference\. • Medium η\\eta: When η\\eta takes a moderate value \(0\.4−0\.70\.4\-0\.7\), the results indicate that most of the difference magnitude is at a medium level\. This suggests that within this range of η\\eta, the repetitiveness and randomness of text sequences are relatively balanced\. An increase in the number of truncations does not result in extreme variations in compression performance; in some cases, a well\-designed segmentation strategy may even moderately improve compression efficiency\. • High η\\eta \(close to 1\.01\.0\): When the η\\eta value is high, the text is more structured with a greater number of repeated subsequences\. In this case, segmentation does not significantly enhance or degrade the compression performance of Ladderpath\. The above results show that for a text sequence of about 1000 lengths in this experiment, the split has a small effect on the compressed length\. The average difference between splits and original sequences is mostly in the range of \-2 to 0\.5, which is negligible\. Sequences with different η\\eta values have different sensitivities to truncation; the larger the η\\eta value and the more organized the sequence, the weaker the effect of truncation on the compression effect\. In any case, we can see that the truncation of text does not significantly change the compression result, thus verifying the feasibility of reducing the complexity of the algorithm by cutting the sequence\. Appendix E Tie\-breaking details in kk\-NN kk\-NN is a widely used algorithm for classification tasks due to its intuitive approach\. The fundamental idea is to classify a sample by identifying the nearest kk neighbors in the training set\. Based on the distribution of categories among these neighbors, the sample’s category is determined through voting or a weighted decision\. However, challenges arise when there is a tie in the votes among the kk neighbors\. There are various strategies for dealing with this problem: \(1\) Random: The label of a randomly selected neighbor in the flat ticket category is assigned to the sample to be classified; \(2\) Nearest: Among the neighbors of the tie\-ballot, rank them according to their distance from the sample to be classified and assign the label of the nearest neighbor to that sample\. After resolving the tie vote, researchers usually evaluate classification accuracy by comparing predicted labels with true labels\. In the context of the study conducted by Jiang et al\. \(k=2k=2\), it did not use Random or Nearest methods when facing a tie\. Instead, it directly analyzes the labels of the two neighbors to provide results on classification accuracy\. Their strategies for interpreting tie votes are: • Optimistic: Under this strategy, the prediction is considered correct if at least one of the two neighbors’ categories matches the true category during a tie scenario\. • Pessimistic: This approach demands that both neighbors must agree with the true category for the prediction to be deemed correct when a tie occurs\. Table 9 and 9 presents the outputs from the two decision\-making strategies when k=2k=2, with W representing wrong classifications and C representing correct classifications\. The results indicate that the Optimistic strategy achieves a correctness rate of 3/43/4, while the Pessimistic strategy yields a significantly lower correctness rate of only 1/41/4\. Although the original article mentions a Random method, it was not practically used\. This is likely due to the fact that with k=2k=2, the Random choice can result in a 50%50\\% error probability, which does not meaningfully enhance performance\. Table 8: Pessimistic decision\-making\. Table 9: Optimistic decision\-making\. Ultimately, the authors in the reference \(Jiang et al\., ACL 2023, pp\. 6810–6828\) opted for the optimistic strategy, which contributed to the relatively high accuracy of their results \(albeit slightly unrealistically high\)\. In this study, we have chosen to implement the Nearest method for resolving the tie vote problem, which provides a fairer comparison\. Table 10 gives the comparison results on multiple datasets using Nearest and Optimistic strategies\. The difference in performance of Nearest over Optimistic with k=2k=2 is clearly visible, which is why the data in the original article is inflated\. Table 10: Performance comparison of different decision\-making methods under k=2k=2\. Appendix F Out\-of\-distribution case with k=2k=2 Table 11: Comparison of text classification accuracy across different models on five OOD datasets \(k=2k=2\)\. Appendix G Out\-of\-distribution case in few\-shot setting with k=2k=2 Table 12: Comparison of text classification accuracy across various methods on OOD datasets in the 5\-shot setting using different methods with k=2k=2\.`