---
kind: concept
slug: laplacian-smoothing
title: Laplacian smoothing
summary: >-
  Add a fixed pseudo-count beta to every next-symbol count so no symbol gets probability zero (add-beta, add-one when beta = 1). Covers the estimator, the order-k context, and what a one-layer Mamba must represent to compute it in context. Trade-offs: beta is a prior choice the paper does not sweep, and a recurrent state needs about 2^k hidden units for order k. Numbers are author-reported.
tags: [smoothing, count-based-estimation, markov-chains, in-context-learning, state-space-models]
papers: ["2502.10178"]
related: [state-space-model, in-context-learning, label-smoothing]
status: draft
updated_at: 2026-11-06
---

## 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 [arxiv: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 [arxiv:2502.10178 §1]. The minimax part holds in the limit of
long sequences [arxiv:2502.10178 app. E]. The name is shared with
[label smoothing](/concepts/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
[arxiv:2502.10178 §2.1, §2.4, app. A]. The experiments do not state a beta
value. The repository fixes beta = 1 [code: src/optim/utils.py#L9-L14]; see
[Contradictions](#contradictions).

Card: [From Markov to Laplace: How Mamba In-Context Learns Markov Chains](/papers/2502.10178).

### 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
[arxiv: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 [arxiv:2502.10178 §2.4]. The paper
sweeps orders 1 to 4 [arxiv: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) [arxiv:2502.10178 §4.3, app. D].
The experiments show that d = 2^k is enough for the order-k case
[arxiv: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 [arxiv: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 [arxiv:2502.10178 §4.2, app. C.2]. A binary-case
variant with d = N = 2 matches only up to a KL error epsilon
[arxiv:2502.10178 §4.2, app. C.3].

Card: [From Markov to Laplace: How Mamba In-Context Learns Markov Chains](/papers/2502.10178).

## When to use which

| Situation | Use | Why |
|---|---|---|
| Counts are available in the prompt and no training is possible | Add-beta with beta set from the assumed prior; beta = 1 for a uniform prior | The add-beta estimate is Bayes-optimal under the matching Dirichlet prior [arxiv:2502.10178 §2.4, app. A]. The paper's own setup uses a uniform prior [arxiv:2502.10178 §2.1]. |
| First-order context, a fixed-size recurrent state, and a model you can edit | Add a convolution with window 2 before the state update, with state size equal to the alphabet size | The exact construction uses w = 2 and N = S [arxiv:2502.10178 §4.2, app. C.2]. Trained weights do not look like the construction, so check the counts empirically [arxiv:2502.10178 fig. 5]. |
| Order k above 1 in a recurrent state | Budget a hidden size of about 2^k, and expect a fixed-size model to fall short below that | Lower bound and matching experiments [arxiv:2502.10178 §4.3, app. D, fig. 6]. |
| Model must learn the counts from data | Keep the convolution in the block | Removing it stops learning on Markov data [arxiv:2502.10178 fig. 3]. On WikiText-103 the same removal raised perplexity from 27.55 to 30.68 [arxiv:2502.10178 tab. 4]. |
| Short prompts | Expect a large gap to the optimum at the start of the sequence | The trained model's gap to the optimum is 0.378 at t = 1 and 0.001 at t = 300 on the hold-out split [arxiv:2502.10178 tab. 2]. |

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

```pseudocode
# 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
[arxiv: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 [arxiv:2502.10178 §2.1] [code: src/optim/utils.py#L9-L16].
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](/papers/2502.10178): 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.