CALLIOPE · BCOM

We formalize the use of large language models (LLMs) as practical compressors to evaluate and optimize ontologies for a text corpus. The uncomputability of Kolmogorov complexity (K(x)) prevents exact evaluation of the best two-part code for data (x), but modern LLMs provide accurate predictive distributions that, combined with arithmetic coding, yield near-Shannon code lengths and actionable upper bounds on (K(x)). We (i) define an ontology (O) as a model component within a two-part description length (L(O;x)= (O)+ (x! !O)), (ii) show how LLM-based coding supplies a computable surrogate for ( (x! !O)), (iii) connect the resulting trade-off to Kolmogorov's structure function (h_x( )), and (iv) outline an experimental protocol. We back the approach with recent results demonstrating that LLMs are effective lossless compressors across modalities {deletangLanguageModelingCompression2024b}{http://arxiv.org/abs/2309.10668}, {valmeekamLLMZipLosslessText2023}{http://arxiv.org/abs/2306.04050}, {liUnderstandingCompression2024a}{http://arxiv.org/abs/2407.07723}, {liLosslessDataCompression2025}{https://www.nature.com/articles/s42256-025-01033-7}, and that compression ability tracks model capability {huangCompressionRepresentsIntelligence2024}{http://arxiv.org/abs/2404.09937}. We also note current gaps exposed by compression-as-intelligence code-generation benchmarks {yoranKoLMogorovTestCompression2025}{http://arxiv.org/abs/2503.13992}.

A compression-theoretic framework for scoring and improving ontologies using LLMs as stand-ins for an uncomputable ideal.

The core idea is simple: a good ontology should make a corpus easier to describe. If you encode the ontology itself, then encode the corpus given that ontology, the total bit count should be smaller than encoding the corpus alone. This is the classic minimum description length (MDL) trade-off — pay a little upfront for the model, save a lot on the data. The problem is that the theoretically ideal version of this (Kolmogorov complexity) is uncomputable. You can never actually find the shortest possible description of anything non-trivial.

The paper's move is to replace the uncomputable ideal with something practical: an LLM acting as a lossless compressor. The key insight, well-established in the literature the paper cites, is that any next-token predictor can be turned into a lossless compressor via arithmetic coding — a technique that assigns shorter bit strings to more probable sequences. If the LLM assigns high probability to the next token, you spend fewer bits encoding it. So the LLM's cross-entropy loss on the corpus, conditioned on the ontology, directly measures how many bits you'd need to encode the data given that ontology. This is computable, and recent work shows LLMs are already state-of-the-art lossless compressors across text, images, audio, and video.

The paper then formalizes ontology optimization as minimizing the sum of two quantities: the bit cost of serializing the ontology itself (gzipped JSON, say), plus the LLM's cross-entropy on the corpus after the ontology has been applied (entity canonicalization, type tags, relation markers, etc.). It connects this to Kolmogorov's structure function — a theoretical curve describing how residual data complexity drops as you invest more bits in a model. The paper proposes tracing an empirical version of this curve by sweeping ontology complexity and watching where codelength drops sharply, which signals that a genuinely useful regularity was captured.

The practical protocol is: generate candidate ontologies with an LLM toolchain, render the corpus through each ontology (substituting canonical terms, inserting type annotations), measure the resulting codelength, and search over ontology edits — merging classes, retiring aliases, adding relations — to minimize total description length. The paper is honest about limits: LLMs don't reach the Solomonoff universal prior, and the KoLMogorov Test benchmark shows current models struggle badly when compression requires actual program synthesis rather than next-token prediction. The proposed remedy is pragmatic — use LLMs for local statistical regularities, and reach for symbolic tools where needed.

This is a theoretical framing paper with an outlined experimental protocol rather than reported results. It does not present empirical measurements of its own. Its contribution is conceptual: giving BCOM a principled, quantitative criterion for ontology quality that is grounded in information theory and operationalizable with existing tools.