Laplacian smoothing

Overview

Laplacian smoothing predicts the next symbol from counts. It takes how often each symbol followed the current context earlier in the sequence and adds a constant beta to every count, so that unseen symbols keep a non-zero probability 2502.10178 §2.4. For binary symbols the estimate of the probability of symbol j is (n_j + beta) / (n + 2 beta), where n_j counts the followers of j, and n counts all occurrences of the context [arxiv:2502.10178 §2.4]. With beta = 1 this is Laplace's add-one rule. The paper calls the general form the add-beta estimator.

The authors report that, for random Markov chains, this estimator is Bayes and minimax optimal 2502.10178 §1. The minimax part holds in the limit of long sequences 2502.10178 app. E. The name is shared with label smoothing, which softens training targets and is a different technique.

The invariant all variants share is this: the prediction is a count-based posterior mean under a symmetric Dirichlet prior, so it adds mass to every symbol in proportion to the prior, not to the data [arxiv:2502.10178 §2.4, app. A].

Variants

Add-beta with a chosen pseudo-count

Rows of the transition table are drawn from Dirichlet(beta) with beta > 0, and the add-beta estimate is the Bayes-optimal predictor for that prior 2502.10178 §2.1, §2.4, app. A. The experiments do not state a beta value. The repository fixes beta = 1 utils.py; see Contradictions.

Card: From Markov to Laplace: How Mamba In-Context Learns Markov Chains.

Add-one (beta = 1)

With beta = 1 the prior is uniform over each row. In the trained one-layer Mamba, the count-independent part of the output logit converges to beta = 1 2502.10178 §3.

Order-k contexts

For order k, the context is the last k symbols, and the counts are taken over the k-symbol histories seen in the prompt 2502.10178 §2.4. The paper sweeps orders 1 to 4 2502.10178 fig. 3. For a recurrent model the cost of order k is the hidden size: any recurrent model with hidden size d and p-bit precision that reaches error epsilon in the L-infinity norm needs d * p >= 2^k (1 - 3 epsilon) log(1/epsilon) 2502.10178 §4.3, app. D. The experiments show that d = 2^k is enough for the order-k case 2502.10178 §4.3, fig. 6.

Learned in a Mamba block versus hand-built

A trained one-layer Mamba matches the add-beta predictor closely on first-order chains 2502.10178 §3, fig. 1. For first-order chains a hand-built Mamba block with convolution window w = 2, embedding size d = 2S, state size N = S and expansion 1 reproduces the estimator exactly for every sequence and every position 2502.10178 §4.2, app. C.2. A binary-case variant with d = N = 2 matches only up to a KL error epsilon 2502.10178 §4.2, app. C.3.

Card: From Markov to Laplace: How Mamba In-Context Learns Markov Chains.

When to use which

Implementation sketch

Add-beta estimate for an order-k context over S symbols. The paper states the binary case; the general form is the standard one.

# Add-beta (Laplacian) next-symbol estimate  [§2.4] [app. A]
# past: list of symbols in {0..S-1} seen so far; k: Markov order
def add_beta_estimate(past, k, beta, S):
    # Current context: last k symbols of the prompt  [§2.4]
    context = past[-k:]
    # n_j: times symbol j followed this context earlier in the prompt  [§2.4]
    counts = zeros(S)
    for i in range(k, len(past)):
        if past[i - k:i] == context:
            counts[past[i]] += 1
    # n: total occurrences of the context, the sum of the counts  [§2.4]
    total = sum(counts)
    # Add beta to every count; for binary symbols this is (n_j+b)/(n+2b)  [§2.4]
    return (counts + beta) / (total + S * beta)

The inner loop is quadratic in the prompt length. A recurrent model avoids it by keeping the counts in its state, which is where the 2^k bound applies 2502.10178 §4.3.

Contradictions

No disagreement between papers: only one card lists this concept.

Within the source, the text allows any beta > 0 for the prior, while the experiments leave beta unstated. The repository draws each row uniformly on [0, 1], which is beta = 1, and has no option to change it. Its count estimator also defaults to beta = 1 2502.10178 §2.1 utils.py. Treat beta = 1 as the value the reported results used, and treat other values as untested.

Papers

• From Markov to Laplace: How Mamba In-Context Learns Markov Chains: shows a one-layer Mamba learns the add-beta estimator in context, names convolution as the key block, gives an exact first-order construction, and bounds the recurrent hidden size for order k.