Sampler: implement XTC (eXclude Top Choices)

[pekkah]

Motivation

Related to #464 and #465, but attacking the cause rather than the pattern — and worth stating precisely, because I lumped all three together loosely when raising them.

DRY and no-repeat-ngram detect repetition and suppress it. XTC does not look at history at all: it targets the peakedness that makes replay inevitable. The measurement behind #463 established that verbatim replay on a 12B roleplay model came with per-step p(max) ≈ 1 — four requests with independent entropy-seeded RNGs at temperature 0.85 produced byte-identical multi-hundred-token replies, which is only reachable if the distribution collapsed to one candidate per step. No token-level penalty fixes that; the model is simply certain. XTC is the sampler that removes the certainty.

What it is

Introduced by @p-e-w for text-generation-webui, now in llama.cpp (--xtc-probability / --xtc-threshold). After softmax, with probability xtc_probability:

• find all tokens with p >= xtc_threshold (typically 0.1)
• remove all of them except the least probable one

So when the model is confident and several strong candidates exist, the strongest are dropped and a viable-but-not-obvious continuation is taken instead. When only one token clears the threshold it is kept — XTC never leaves the distribution empty and never forces a low-quality token, which is what separates it from just raising temperature.

Parameters: xtc_probability (0 = off; 0.5 typical), xtc_threshold (0.1 typical; above 0.5 it is a no-op by construction).

Why it is not redundant with the other two

• It is stochastic and stateless — no history scan, so it costs nothing and cannot be defeated by a long enough context.
• It breaks out of a rut rather than forbidding the rut. A model deep in a copy attractor still has coherent alternatives; XTC takes one.
• Conversely it is the wrong tool when correctness matters: it deliberately discards the top choice, so it should not be on for code, tool arguments, or grammar-constrained output. Worth documenting as such.

Implementation notes

• Runs after softmax and, per llama.cpp's chain, before min-p/top-p. Ordering relative to the existing filters must be pinned deliberately — Sampler's pipeline order is already load-bearing and documented (top-k → renormalise → min-p → top-p).
• Both paths: Sampler.Sample's slow path and SampleTopK. In the fast path the removed tokens are by definition inside the candidate set, so no change to the over-select; but XTC promotes lower-ranked survivors into contention, so check whether the promotingPenalty reasoning at Sampler.cs:40-41 needs an analogous case — I believe not, since every token it promotes is already within top-k, but that should be argued explicitly in the PR rather than assumed.
• Needs a Random draw per token. Both engines already create one per request (InferenceEngine.cs:685); Sampler.Sample already receives it. BuildFilteredDistribution is deterministic and is used for speculative decoding's q(x)/residual — a stochastic sampler breaks the shared-support assumption that the min(1, p/q) accept ratio depends on. Decide and document: most likely XTC must be excluded from the speculative path, or the draw threaded through so draft and target agree.
• Interaction with ITokenConstraint: XTC must not remove the last constraint-legal token. Needs a guard and a test.
• Surfaces per the fix(server): expose repetition_penalty and penalty_last_n per request #461/feat(server): per-request top_k and min_p #462 convention.

Tests

tests/SharpInference.Tests.ForwardPass, model-free with a seeded Random: assert that at probability = 1 and a known threshold the expected tokens are removed and the least-probable above-threshold one survives; that a single above-threshold token is never removed; that probability = 0 is byte-identical to no XTC; and that support is never emptied.

References

• llama.cpp llama_sampler_xtc — src/llama-sampling.cpp
• Original proposal: Exclude Top Choices (XTC): A sampler that boosts creativity, breaks writing clichés, and inhibits non-verbatim repetition oobabooga/textgen#6335