sortpoison

Do llama.cpp's truncation samplers honor the sorted-flag contract, or can a stale flag make top_p, min_p, and top_k truncate the mathematically wrong set of tokens?

llama_token_data_array carries a boolean sorted flag; the public header warns "do not assume the data is sorted - always check this flag". The truncation samplers have a fast path: when sorted == true they skip re-sorting and read a prefix of the array in its current order (top_p and min_p also trust data[0] as the maximum). A sampler's survivor SET is, by definition, a function of the logit multiset and the parameter only, so it must be invariant to input order. This repo tests, exhaustively over the real shipped code, whether that invariant holds when the flag is stale, and whether a stale flag is reachable through the public sampler API.

Result

Three of the four truncation samplers are unsound under a stale sorted = true flag, and the stale state is reachable through a documented public-API sampler chain.

• top_p, min_p, and top_k are order-dependent when handed sorted = true on an array that is not actually sorted. Exhaustively enumerating all n! permutations of a fixed logit multiset (linked against the real libllama, calling the shipped llama_sampler_apply) yields many distinct survivor sets for the same multiset: up to 11 distinct sets for top_p, 8 for min_p, 10 for top_k. A correct truncation sampler cannot return different token sets for the same multiset, so this is a proof of unsoundness, not a measurement. Every order-dependent set differs from the correct set.
• typical is sound. It re-sorts fully by its own key and resets sorted = false, so its output is permutation-invariant (exactly one set across all permutations).
• The bug is a broken invariant, not bad luck. A fast path that trusts sorted is only safe if every sampler that reorders logits resets the flag. penalties, dry, and typical all reset it; logit_bias does not. It adds a caller-supplied bias to arbitrary tokens (an arbitrary reordering) and leaves sorted untouched. grammar and xtc also reorder without resetting it. logit_bias is the cleanest injector.
• Reachable through the public API. The chain top_k(4) -> logit_bias(+6 @ id3) -> top_p(0.80), built with llama_sampler_chain_add and run through llama_sampler_apply, keeps the survivor set {0,1,2,3} where the correct set is {3}. top_k sets sorted = true; logit_bias moves a token to the front of the true order while the flag stays true (the harness observes sorted == true after the logit_bias step); top_p then reads the stale prefix. The correct answer keeps only the biased token (about 94 percent of the mass); the buggy path keeps it plus three low-probability tokens, diluting the distribution a downstream selector samples from.

Consequence and honest scope

When a stale sorted = true reaches top_p, min_p, or top_k, the truncation set is wrong: tokens that should be cut survive, and the renormalized distribution the next stage samples from is not the one the parameters specify. In the reachable chain the effect is large (keep 4 where 1 is correct).

Scope, stated plainly: the stock common sampler chain in common/sampling.cpp prepends logit_bias and grammar before any sorter, so the default llama-cli and llama-server chains are not affected. The bug is reachable for any consumer that constructs a chain through the public llama_sampler_chain_add API with a reordering sampler placed after a sorter, which is possible for servers, language bindings, and custom sampler stacks that order samplers freely (stated as a capability of the public API, not a cited downstream instance). This is a latent-until-ordered soundness bug in a production component, in the spirit of a contract that the fast path assumes but the codebase does not fully enforce. reach.md is the full static audit of which samplers keep the invariant.

Why the certification is trustworthy

• Real subject. The harness links the shipped libllama (Homebrew build 9760, commit 6ee0f65793) and calls the public llama_sampler_init_* / llama_sampler_apply / llama_sampler_chain_* symbols. Harness-eval is production-eval; nothing is transcribed.
• The proof is order-variance itself. Distinct survivor sets for one multiset is unsoundness by definition, needing no external oracle. The independent clean-room reference (ref.py) then confirms the honest-flag output is the mathematically correct set (0 mismatches over 8 cases), so the stale-flag sets are genuinely wrong.
• Negative control. With the honest flag (sorted = false), every sampler returns exactly one set across all n! permutations, proving the samplers are order-invariant when the flag is honest, so the variance is caused by the stale flag, not the harness.
• Positive control. A deliberately stale (reverse-sorted) array fed to top_p with sorted = true returns a set that differs from the honest set, proving the detector fires.
• Boundary-tie-free inputs. Multisets use distinct logits with truncation thresholds landing strictly between probability levels, so every reported difference is a genuine wrong token, never a tie-rule disagreement.

Run

./run.sh          # builds harness vs libllama, runs the audit + controls + reachability, cross-checks the reference

Needs the Homebrew llama.cpp headers/lib at /opt/homebrew. Fully CPU, exact, deterministic; no timing, no probability sampling.

Files

• harness.cpp — links libllama; exhaustive permutation audit under forced sorted, negative/positive controls, and the public-API reachability chain (manual and real llama_sampler_chain).
• ref.py — clean-room order-invariant set-functions; cross-oracle against llama.cpp's honest path.
• reach.md — static audit of every sorted write: which samplers keep the invariant, which break it.
• PREREG.md — the pre-registration.
• results/ — machine-checked outputs.

License

MIT.