CS Paper Radar

Information Theory of Random Composition Trees

Doron Sivan, Weishun Zhong, Tankut Can, Mikhail Katkov, Misha Tsodyks

cs.IT cs.CL ·submitted 2026-10-17 17:27 UTC · v1
theory

Abstract

Random composition trees model the hierarchical semantic structures of meaningful texts as a statistical ensemble generated by recursively splitting texts into coherent chunks. A recent study shows that different text types can be described by random composition trees with distinct branching factors, and that the entropy rates of these trees exhibit a similar dependence across text types as the entropy rates of the actual texts. Motivated by this correspondence, we analyze information-theoretic properties of this stochastic splitting model. First, we demonstrate that the entropy of random composition trees grows linearly with the root size, and we derive an analytical expression for the entropy rate as a function of the branching factor. Second, we prove that large trees exhibit typicality: with high probability, they belong to a typical set in which each tree is approximately equally likely. Our analysis reveals that the random composition tree model shares two key information-theoretic properties of language when modeled as a stationary and ergodic stochastic process: linear entropy growth and typicality.

Closest papers

Nearest neighbours by meaning across the whole index.

The Probabilistic Structure of Large Language Models

cs.LG cs.AImath.PRstat.ML ·2026-09-20 ·Adnan Aboulalaâ
similarity 0.60
Abstract · Expository article on the probabilistic structure of large language models, 27 pages

This paper presents a probabilistic perspective on large language models (LLMs), developed with the aim of bringing together, in a single self-contained account, tools that are usually treated separately across the literature. LLMs are described through probability measures on the set of sequences of tokens, specified via their autoregressive conditional distributions. Training is formulated as a maximum-likelihood estimation problem, addressed by stochastic gradient methods, while text generation is viewed as the sequential simulation of the resulting stochastic process. The role of the asymmetry of the Kullback--Leibler divergence in text generation is examined in relation with characteristic phenomena such as hallucination and the distinction between statistical plausibility and truth. As a complementary illustration of the same viewpoint, we also discuss diffusion models, built around the score function, which cast generation not as sequential token prediction but as the simulation of a reverse-time stochastic process transforming noise into data both in discrete and continuous time.

0.32

A Data-free Universal Prior over Syntactic Structures

cs.CL cond-mat.dis-nn ·2026-09-15 ·Fermín Moscoso del Prado Martín
similarity 0.56
Abstract · 30 pages, 4 figures

The probabilities of syntactic structures in human languages are assumed to emerge fully from language-specific experience. Here, I show that a universal prior over syntactic structures emerges from a model of human language production, in which words are progressively integrated into syntactic structure. Without fitting any parameters to specific language data, the resulting prior assigns higher probabilities to attested than to random dependency trees in all 138 typologically diverse languages examined. These prior probabilities correlate positively with those estimated from corpora in 33 of 34 languages. The results indicate that part of the probability structure of syntax can arise independently of language-specific learning. This identifies human language production as a possible cognitive source of universal statistical structure in language, while providing a data-independent structural bias for probabilistic models, including large language models.

0.21

Power-Law Correlations Without Apparent Temperature-Tuned Criticality in Fixed-Tree Hierarchical Languages

cs.LG cond-mat.dis-nn ·2026-10-17 ·Marcel Kühn, Bernd Rosenow
unusual similarity 0.55
Abstract · 19 pages, 6 figures

Sampling temperature can substantially reshape autoregressive generation, but it is unclear when temperature changes in long-range correlations reflect a genuine phase transition rather than a smooth change in statistics. We study this question in a controlled analogue of temperature sampling: a finite-depth probabilistic context-free grammar on a fixed hierarchical tree, where exact next-token conditionals are computed by belief propagation and then rescaled by a softmax temperature before autoregressive sampling. We measure two-point mutual information between tokens as a function of separation. Across the tested temperatures and grammar ensembles, mutual information remains well described by a power-law envelope. Temperature changes the correlation magnitude and fitted exponent, but within the accessible system sizes we find no long-distance plateau characteristic of an ordered phase and no clear crossover to short-range exponential decay. An approximate mapping to an Ising model on a tree explains how exponential decay in tree distance becomes a power law in token distance, allowing power laws to persist without tuning to a special decoding temperature. This controlled baseline clarifies which temperature effects can arise from hierarchical structure alone, before adding training, approximation error, or neural architecture.

0.26

What Does Chain-of-Thought Entropy Measure? A Channel Audit of Scaffolding, Routing, and Content

cs.IT stat.MLcs.LG ·2026-08-26 ·Marios Papamichalis, Regina Ruane
theoryhot direction similarity 0.55
Abstract

Entropy over chain-of-thought tokens decides which tokens receive the policy gradient, which get pruned, and whether a run has collapsed, yet each such statistic reads a next-token distribution mixing three choices: whether to emit connective scaffolding, which connective, and what the substantive continuation should be. Designating a scaffold vocabulary subset separates the three, exactly, for entropy, Kullback--Leibler divergence, and the first-order entropy velocity of a softmax policy. We prove the raw and content conventions disagree about which position is the larger fork on an explicit open region, and bound answer diversity by the content channel plus a leakage term a measured witness certifies. Across twenty-three configurations the scaffold side carries up to 41% of the raw high-entropy set; on a matched-tokenizer ladder, coupling changes only at the math-corpus step while the scaffold's entropy share keeps growing through distillation; a closed-form forecast from one channel correlation tracks selection retention over a 54-point range to five points, unfitted. On compression, the content convention beats raw surprisal in every cell; an answer-leakage audit then corrects our own headline control: re-fed chains earn a quarter to a half of their accuracy from restated answers, and once stripped, no token scorer beats a random contiguous block.

0.33

Taxonomy-aware distances between scholarly topic profiles via an exact simplex embedding

cs.DL ·2026-08-23 ·Dmitry Gubanov, Alexander Chkhartishvili
similarity 0.54
Abstract

Topic profiles represent publications, authors, and other scholarly entities as probability distributions over a fixed set of topics, but flat total variation treats every pair of distinct pure-topic profiles as maximally separated and therefore ignores taxonomic proximity. From a rooted weighted taxonomy, we derive a cardinality-normalized linear operator that maps the leaf topics to points in the original probability simplex and exactly realizes a normalized lowest-common-ancestor ultrametric under total variation. The operator is doubly stochastic and positive definite; within the class of nonnegative edge-cluster Gram operators, its normalization is uniquely determined on the reduced branching tree. Applying the same invertible operator to arbitrary topic mixtures yields a nondegenerate hierarchy-aware metric that contracts flat total variation, differs from the tree-Wasserstein distance on mixtures, and can be evaluated in O(|V|+L) time and memory without forming the dense matrix. In a frozen OpenAlex taxonomy with 4,516 terminal Topics, raw dissimilarities between Topic texts showed consistent ordinal alignment with taxonomic proximity, while only 3 of 253 calibrated internal nodes required monotonic correction. Encoder choice nevertheless affected individual height estimates. The framework exactly realizes a supplied weighted hierarchy; text is used only to initialize its node heights, and distances between scholarly topic profiles are then computed in the induced geometry.

0.24

Rarity Determines Minimax Rates of Semantic Entropy From Weak Pairwise Judgments With a Known Channel

cs.IT cs.LG ·2026-10-13 ·Xiaoli Yu, Jiamiao Liu
code/data similarity 0.54
Abstract · 39 pages, 7 figures, 7 tables. Code: https://github.com/yahiko-l/semantic-entropy-rarity

The semantic entropy of a language model is the entropy of the meanings of its sampled answers. The meanings are never observed, and the entropy is estimated from the verdicts of a pairwise equivalence judge. Given the meanings of $n$ answers, a known channel declares each pair equivalent independently, with probability $q+Δ$ within a meaning and $q$ across meanings. At most $K$ meanings occur, and $q$ is bounded away from $0$ and $1$. For a weak judge, with $nΔ^2\to0$, the global minimax rate is set by distributions near a vertex of the simplex and overstates the difficulty elsewhere. We show that the difficulty is set by how many meanings can be rare. Over distributions with at most $s$ meanings below a fixed probability $τ<1/(K-s)$, the minimax squared risk is of order $N^{-1/s}$ for $s\ge2$, $N^{-1}\log^2(e+N)$ for $s=1$ and $N^{-1}$ for $s=0$, capped at one, where $N=n^KΔ^{2K-2}$. The matching lower bounds hold on every fixed polynomial window $nΔ^2\le n^{-κ}$. One estimator attains these rates without knowing $s$ or $τ$: it averages products of centered verdicts along all spanning trees of every $k$-set of answers, projects the resulting power sums onto the valid moment set and inverts them. The case $s=K-1$ gives the global rate $N^{-1/(K-1)}$ and the consistency threshold: with $Δ=n^{-γ}$ the entropy is uniformly consistently estimable exactly when $γ<K/(2K-2)$. On polynomial windows, the same estimator attains the sharp local minimax constant on shrinking neighborhoods of interior points with distinct probabilities. Restricting the average to stars multiplies the constant by $K^{K-3}$.

0.45

What's in a Tree ? Hierarchical $n$-gram models as controlled approximators of language

cs.CL cond-mat.dis-nncs.AIcs.LG ·2026-11-17 ·Aritra Das, Francesco Cagnetta, Darshil Doshi, Victor V. Albert, Maissam Barkeshli +1 more
similarity 0.53
Abstract · 7+13 figures, 10+30 pages

Hierarchical models have been proposed as synthetic settings for studying language. However, their relevance to realistic language corpora remains underexplored. In this work, we introduce tree-grams, autoregressive generative $n$-gram models that build the conditional probability tensor $p(x_n \mid x_{1:n-1})$ through a hierarchical composition of order-2 and order-3 tensors. $n$ controls the maximal context window, whereas a rank hyperparameter $d$ controls model capacity, yielding an interpretable and systematically scalable family of approximators of language. We show how tree-grams outperform existing $n$-gram baselines, while remaining competitive with deep transformer-based language models. We demonstrate the utility of such controlled approximations by using tree-grams as generative models. In particular, we show that hyperparameter transfer under $μ$P can be made more robust when narrower models are tuned on simpler data, generated by tree-grams with moderate $n$ and $d$. In addition, we show that entropy and effective range of correlations control performance gap after fine-tuning. This is because tree-grams allow us to explicitly control horizon and capacity. When allowed to route across candidate topologies, we observe emergent sparsity in tree-grams. Such concentrated routing permits pruning upto 95\% of topologies without significant change in performance.

0.21

Emergent phases of superposition: from partial to full representation

cs.LG ·2026-09-29 ·Lihao Guo, Yizhou Liu, Jeff Gore
similarity 0.53
Abstract · 35 pages, 25 figures

Large language models are thought to represent features by vectors in a hidden space of dimension given by the model's width. Superposition, in which more features are represented than the width by letting representation vectors overlap, is a leading account of how representation vectors are organized. However, how model width and data statistics determine the configuration of representation vectors and the resulting loss when the number of features and the width are large remains less understood. Here we show, in Anthropic's toy model of superposition, that increasing the width drives a continuous phase transition from a partial-representation phase, where only a subset of features receives appreciable representation vectors while the rest vanish, to a full-representation phase, where every feature is represented. Our theory via a partial random projection approximation predicts, and experiments confirm, that the critical width grows linearly with the number of active features up to a logarithmic factor. The loss scaling changes across the transition: below the critical width, the loss grows linearly with the number of active features and depends weakly on the width in a form set by data statistics; above it, the loss grows approximately quadratically with the number of active features and decays inversely with the width. Non-uniform firing probabilities delay the transition and lower the loss, as more frequent features occupy more space. Our results provide an account of how model width and data statistics jointly shape representations and loss, a step toward understanding representation scaling in large models.

0.21