A Layered Simplex Architecture for Large Alphabets

Meir Feder; Yaniv Fogel; Ruediger Urbanke

cs.ITAug 20, 2026

A Layered Simplex Architecture for Large Alphabets

Authors: Meir Feder, Yaniv Fogel, Ruediger Urbanke

Organizations: School of Electrical and Computer Engineering Tel Aviv University, Tel Aviv, Israel · School of Computer and Communication Sciences EPFL, Lausanne, Switzerland

Abstract

Probability estimation over large alphabets under log loss is a well-studied problem, with celebrated methods such as the Good-Turing estimator. We introduce and study a new Bayesian estimator with four notable properties. First, its construction is exceptionally simple: multiply independent uniform draws from the probability simplex coordinate-wise and renormalize. Depth is the only structural parameter, and averaging over depths eliminates the need to tune it. Second, the regret of the resulting mixture, the excess code length it pays relative to a code that knows the source, admits an explicit and efficiently computable expression. Third, despite its simplicity and lack of tuned constants, the estimator is competitive across a diverse set of synthetic and real-text benchmarks with substantially more specialized methods, including Good-Turing. Fourth, the tractability of its regret allows us to identify scaling laws in data, alphabet size, and depth. For Zipf targets with exponent above one, the regret has a simple reading as long as the sample reveals only a small fraction of the alphabet. It closely matches the description length of the set of discovered symbols, at one bit of code per bit of description, plus a further cost per symbol. The data exponent is therefore the rate at which new symbols are discovered.

Figures & tables

Panel of Figure 1 — Figure 1: One draw of the layered simplex architecture (LSA) at $d=24$ , $L=4$ (real draws, common vertical scale). Each layer is an independent uniform draw from the simplex, every coordinate fluctuating around the common scale $1/d$ . Multiplying the layers coordinatewise and renormalizing yields a draw $\theta$ from the LSA prior $\mathcal{M}_{d,L}$ that is sparse and heavy-tailed. The dotted line traces the winning coordinate: it was above average in every layer.

Figure 2: Depth tilts the complexity spectrum at every alphabet size. Online regret on a logarithmic scale versus the Zipf exponent

\alpha

of the target, for

d=10^{3},10^{4},10^{6}

. Every integer depth up to

c=L/\ln d\approx 10

was evaluated; representative depths are displayed for readability. Shallow priors perform best on near-uniform targets, while increasingly deep priors perform best as the target becomes more concentrated. The dashed red curve is the uniform sequence-mixture over all depths

1\leq L\leq L_{\max}

. Its gap from the single-depth envelope is bounded by

(\log_{2}L_{\max})/N

(Remark 1 ); the measured gaps are reported in the text. Error bars are profile-sampling standard errors over

40

sampled profiles.

$\alpha$	0	0.3	0.6	0.9	1.2	1.5	1.8	2.1	2.4	2.7	3.0
best $L$ ( $d=10^{3}$ )	1	1	1	3	6	10	15	23	32	43	47
best $L$ ( $d=10^{4}$ )	1	1	2	4	8	15	24	35	48	63	74
best $L$ ( $d=10^{6}$ )	1	1	4	9	18	33	49	66	85	110	126
envelope ( $d=10^{6}$ )	0.00	0.10	0.79	2.67	2.70	1.49	0.87	0.59	0.40	0.30	0.23
$L{=}1$ ( $d=10^{6}$ )	0.00	0.10	0.80	3.88	8.74	10.63	11.10	11.27	11.31	11.35	11.36

Table 1: Best tested depth per target for the three alphabet sizes of Figure 2 (bits/symbol in the last two rows). Every integer depth up to

c\lesssim 10

was tested; each entry is estimated from

40

sampled profiles. The minimizing depth increases broadly with target skew and with

d

, although the regret curves for the more concentrated targets are shallow and therefore do not identify the minimizing integer depth sharply. None of the nontrivial minima occurs at the upper search boundary.

Figure 3: Symbol discovery. Solid curves give the exact expected number of discovered symbols, dashed curves give the large-sample approximation in Equation ( 10 ), and points with error bars give the mean and standard deviation over

5{,}000

sampled profiles. The effect of the finite alphabet is visible mainly at

\alpha=1.5

and small

d

$\alpha$	measured quantity	$N=10^{2}$	$N=10^{3}$	$N=10^{4}$
$1.5$	slope	$0.87$	$0.76$	$0.58$
	offset $B$ (bits)	$-2.74$	$-2.17$	$-1.34$
$2$	slope	$1.00$	$0.99$	$0.95$
	offset $B$ (bits)	$-0.83$	$-0.64$	$-0.46$
$3$	slope	$1.04$	$1.04$	$1.04$
	offset $B$ (bits)	$1.40$	$1.82$	$1.94$

Table 2: Alphabet scaling. For each

N

, the alphabet size varies from

10^{3}

10^{5}

. Equation ( 12 ) predicts slope one and an offset

B

that does not change with

N

. The table reports both measured quantities.

	simple	$d=10^{3}$		$d=10^{5}$
$\alpha$	prediction	refined	measured	refined	measured
$1.5$	$0.333$	$0.619$	$0.520$	$0.421$	$0.436$
$2$	$0.500$	$0.607$	$0.608$	$0.544$	$0.546$
$3$	$0.667$	$0.696$	$0.689$	$0.678$	$0.672$
$4$	$0.750$	$0.754$	$0.735$	$0.744$	$0.731$

Table 3: Data scaling. Predicted and measured exponents over the tested range

100\leq N\leq 10^{4}

. The simple prediction is

1-1/\alpha

. The refined prediction evaluates the finite-size law on the same values of

N

, with the fixed offset

B=\alpha\log_{2}e-2

bits per discovered symbol; see the text.

Figure 4: Data scaling. The exponent obtained from the measured regret is compared with the simple prediction

1-1/\alpha

and with the finite-size prediction evaluated on the same values of

N

. The refined prediction follows the measurements closely for

\alpha=2

and

3

. At

\alpha=1.5

, it fails for the smallest alphabet, where the sample reveals a substantial fraction of all symbols. At

\alpha=4

, the measured exponent remains slightly below both predictions.

Figure 5: Depth scaling. Measured regret per discovered symbol at

d=10^{5}

and

N=10^{3}

, together with the prediction in Equation ( 14 ). The left panel shows the full range. The right panel enlarges the logarithmic-depth range. The prediction captures the broad flattening near

c^{\star}

, but overestimates it at the shallowest depths, as expected from the approximation used to derive it.

$\alpha$	best tested $c$	$P(c^{\star})/P_{\min}$
$2$	$4$	$1.012$
$3$	$6$	$1.059$
$4$	$6$	$1.095$

Table 4: Depth scaling. Measured dependence of the regret per discovered symbol on depth at

d=10^{5}

and

N=10^{3}

Figure 6: Competitive comparison on the benchmark of [ 17 ] , extended to eleven targets (

d=10^{4}

; log-log axes;

20

trials, standard-error bars). The depth-averaged LSA predictor (red diamonds) performs well on every panel: it matches the best add-constant rule on the flat targets and the best overall rule on eight of eleven panels. On the uniform target, where it lags behind Good–Turing and Ristad, all predictors are far from the natural-oracle curve, which is

\approx 0

	classical						LSA
target	add-1	KT	BS	Ristad	GT	oracle	$L{=}5$	$L{=}22$	avg over $L$
uniform	0.174	0.285	0.262	0.098	0.005	0.000	0.387	0.544	0.174
step	0.180	0.258	0.252	0.152	0.129	0.122	0.344	0.484	0.180
Zipf $\alpha=1$	0.246	0.179	0.219	0.288	0.129	0.120	0.183	0.295	0.154
Zipf $\alpha=1.5$	0.479	0.257	0.268	0.170	0.066	0.061	0.066	0.076	0.066
Zipf $\alpha=2$	0.564	0.310	0.311	0.053	0.027	0.024	0.033	0.026	0.026

Table 5: Mean

D(p\|\hat{q})

in bits at

n=2\cdot 10^{4}

d=10^{4}

20

trials; standard errors

\leq 0.001

bits except the Dirichlet rows (

\leq 0.013

). The last column is the depth-averaged LSA predictor ( 1 ) over all depths

L=1,\dots,80

(see the text), a single prior with no tuned constants. Bold marks rows where it beats every classical (non-LSA) method or ties the best of them within one standard error; Section 5.2 discusses the pattern row by row.

target	posterior over depths at $n=10^{3}$	at $n=2\cdot 10^{4}$
uniform	$L{=}1:1.00$	$L{=}1:1.00$
step	$L{=}1:1.00$	$L{=}1:1.00$
Zipf $\alpha=1$	$L{=}5:0.71,\ L{=}6:0.29$	$L{=}3:1.00$
Zipf $\alpha=1.5$	$L{=}15:0.20,\ L{=}14:0.19,\ L{=}16:0.16,\ L{=}13:0.13$	$L{=}9:0.63,\ L{=}10:0.36$
Zipf $\alpha=2$	$L{=}31,30,32:0.06$ each (broad, $L\approx 26$ to $36$ )	$L{=}24,23,25:{\approx}0.15$ each
Zipf $\alpha=3$	broad: $94\%$ of mass on $L\in[41,80]$	broad, mode $L{\approx}70$ ; $99\%$ on $L\in[41,80]$

Table 6: Mean posterior weights

w_{L}\propto q_{L}(x^{n})

of the depth-averaged predictor (entries below

0.05

omitted). The data select depth as the complexity-spectrum analysis predicts: shallow for flat targets, deep for heavy-tailed ones.

$n$	distinct	$\hat{H}_{n}$	add-1	KT	BS	Ristad	GT	LSA avg	posterior mode
$10{,}000$	1,160	7.56	4.597	3.846	3.805	1.193	1.066	1.052	$L=21$
$30{,}000$	2,119	7.87	3.225	2.512	2.489	0.709	0.606	0.598	$L=21$
$100{,}000$	3,839	8.02	1.911	1.359	1.350	0.381	0.310	0.306	$L=21$
$300{,}000$	6,922	8.18	1.026	0.679	0.677	0.224	0.170	0.168	$L=19$
$915{,}860$	13,550	8.48	0.478	0.303	0.302	0.137	0.097	0.095	$L=15$

Table 7: Compressing the King James Bible (

d=100{,}000

, word-and-punctuation tokens). Redundancy in bits per token (codelength per token minus the empirical unigram entropy

\hat{H}_{n}

) for prefixes of

n

tokens. The depth-averaged LSA predictor is the best method at every prefix length; its posterior over depths is essentially a point mass that drifts from

L=21

down to

L=15

as the sample grows.

Figure 7: The Bible experiment. (a) Redundancy above the empirical entropy for each method as the coded prefix grows (log-log); the depth-averaged LSA predictor (red) is lowest at every

n

. (b) Redundancy of the single-depth mixtures

Q^{(L)}

as a function of depth, at each prefix length; the minimizing depth (dots) moves from

L=21

L=15

n

grows, and the depth-average matches the minimum to four decimal places throughout.

	$M=256$ , $L\leq 40$	$M=512$ , $L\leq 60$
coverage of transitions	$76.6\%$	$83.7\%$
empirical $H(\text{next}\mid\text{state})$	$6.315$	$6.098$
LSA, per-state depth avg	$\mathbf{7.132}$	$\mathbf{7.100}$
Good–Turing (per state)	$7.143$	$7.113$
Ristad (per state)	$7.254$	$7.227$
KT (per state)	$9.781$	$10.172$

Table 8: Order-one models of the Bible (bits per token; unigram reference: empirical entropy

8.477

, LSA code

8.572

). States are the

M

most frequent context tokens plus a backoff state.

Zipf's Law

See all 8 papers

May 20, 2026

Symbolic Density Estimation for Discrete Distributions

Discrete probability laws underpin statistical modeling, yet the catalog of interpretable distributions has expanded only gradually through centuries of case-by-case mathematical derivations. We introduce symbolic density estimation (SDE), an unsupervised framework that automatically recovers closed-form probability mass functions by composing elementary analytic operations within a structured search space. Our method integrates domain-specific structural priors with evolutionary search and a validity-aware inference stage, and it extends to richer distribution families such as zero inflation and finite mixtures. To support systematic evaluation and future research, we contribute a benchmark dataset spanning a broad collection of commonly used discrete distributions. The proposed algorithm recovers all benchmark families with accurate parameter estimates. A real data application shows that it identifies concise and interpretable mixture models that improve goodness-of-fit over standard models.

Ziwen Liu, Meng Li

Rice University Houston, TX

Density Estimation

Ask PDF

Oct 8, 2026

Estimating Great Expectations Under Autoregressive Language Models with Potentials

Many applications of language models require estimating the expectation of a test functional under the model. Obtaining precise estimates can be computationally expensive. We show how to improve estimation precision by exploiting next-token conditional probabilities available as a by-product of sampling. Our approach uses potentials: real-valued functions of prefixes that induce an additive decomposition of the test functional. We construct a family of estimators parameterized by these potentials and derive conditions for variance reduction. Across applications including entropy estimation, watermark detection, and rare-event probability estimation, our estimators achieve substantial variance reductions relative to Monte Carlo and importance sampling baselines at comparable computational cost.

Francesco I. Re, Shubhangi Ghosh, Tim Vieira +1

ETH Zürich · Columbia University

Variance Reduction

Ask PDF

Aug 27, 2026

Sharp Minimax Regret for Infinite-Memory Logistic Prediction

We determine the minimax cumulative log-loss regret of a finite-alphabet, exogenously driven source with genuinely infinite input memory: independent Rademacher inputs

(U_t)

are observed sequentially and the next binary mark has logit

\sum_{j\ge1}θ_jU_{t+1-j}

, the unknown coefficients obeying a summable envelope

|θ_j|\le r_j

\sum_jr_j\le B

. At horizon

T

, lag

j

can move the logit by at most

r_j

and is exercised in only

n_{T,j}=(T-j+1)_+

rounds, and the two limitations combine into the sum

Γ_T(r)=\sum_{j\le T}\log(1+n_{T,j}r_j^{2})

. One coordinate-localised Bayesian mixture achieves

R_T(r)\le CΓ_T(r)

for every summable envelope with

C

universal. Our main result is a matching nonasymptotic converse for the canonical exponential and polynomial envelopes; its new ingredients are a modular finite-sample information bound for logistic experiments with an exogenous random design, and a conditioning estimate for the overlapping Toeplitz lag matrix obtained by exhibiting each off-diagonal Gram sum as a sum of independent Rademacher variables indexed by the edges of a forest, needing neither local asymptotic normality nor any spectral theorem for random Toeplitz matrices. So

Γ_T(r)

is the minimax regret scale here, giving

Θ(α^{-1}\log^{2}T)

for

r_j=Ae^{-αj}

and

Θ(T^{1/(2s)})

for

r_j=Aj^{-s}

s>1

--- the latter without the extra

(\log T)^{1-1/(2s)}

factor any window-truncation analysis pays. We also show memory decay cannot determine regret, and that a profile-scaled online Newton predictor attains

O_B(Γ_T(r))

in polynomial time per round.

Vaneet Aggarwal

Purdue University

Logistic Regression Bayesian Mixture Models Minimax Regret Regret Minimization Information-Theoretic Lower Bounds

Ask PDF

Abstract

Zipf's Law

Explore similar work

Symbolic Density Estimation for Discrete Distributions

Estimating Great Expectations Under Autoregressive Language Models with Potentials

Sharp Minimax Regret for Infinite-Memory Logistic Prediction