# Exact nondecreasing-subsequence constrained decoder

- ID: 1148
- Canonical URL: https://synthcore.org/idea/1148/exact-nondecreasing-subsequence-constrained-decoder
- API JSON: https://synthcore.org/api/idea/1148.json
- API Markdown: https://synthcore.org/api/idea/1148.md
- Verification status: unverified
- Source: [arXiv:2607.19410](https://arxiv.org/abs/2607.19410)
- Category: sampling
- Solves: accuracy, sample-efficiency, generalization
- ML areas: transformer, sampling, data-augmentation
- Math tags: combinatorics, probability, generating-functions, dynamic-systems
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Equip an autoregressive model with a hard constraint that generated token ranks cannot contain a nondecreasing subsequence of length k. Maintain a patience-sorting-style state representing the smallest ending token rank achievable by subsequences of lengths 1 through k-1, mask tokens that would create a length-k subsequence, and optionally sample uniformly among valid continuations using exact suffix counts. This provides a mathematically controlled data-augmentation or decoding regime for symbolic sequences, ranked event streams, or anti-copying benchmarks.

## Mathematical statement

The paper counts n-ary words of length s avoiding a soft streak, interpreted here as a nondecreasing subsequence of length k. Let n be the alphabet size, k the forbidden subsequence length, s the word length, and P(n,k,s) the number of valid words. Its generating function is f_{n,k}(z)=sum_{s>=0}P(n,k,s)z^s=(1-z^k)/Q_{n,k}(z), where Q_{n,k}(z)=sum_{r=0}^{(k-1)n} psi_{k,r}B(n,k,r)z^r. Here B(n,k,r) is the coefficient of x^r in (1+x+...+x^{k-1})^n, and psi_{k,r}=1 when r=0 mod k, -1 when r=1 mod k, and 0 otherwise. Thus, with q_r=psi_{k,r}B(n,k,r) and R=(k-1)n, the valid-word counts satisfy sum_{r=0}^{min(R,s)}q_rP_{s-r}= [z^s](1-z^k)^n, which equals (-1)^{s/k}binom(n,s/k) when k divides s and 0 otherwise. For online constraint tracking, let t_j be the smallest final alphabet rank among nondecreasing subsequences of length j seen so far, for j=1,...,k-1, with t_0=-infinity and all t_j=+infinity initially. For a candidate rank a, define j*(a)=max{j:t_j<=a}; the candidate is invalid if j*(a)=k-1, and otherwise update t_{j*(a)+1}=min(t_{j*(a)+1},a).

## Key formulas

- $$f_{n,k}(z)=\sum_{s=0}^{\infty}\mathcal{P}(n,k,s)z^{s}=\frac{(1-z^k)^{n}}{\displaystyle\sum_{r=0}^{(k-1)n}\psi_{k,r}\mathcal{B}(n,k,r)z^{r}}$$
- $$\mathcal{B}(n,k,r)=[x^r](1+x+x^2+\cdots+x^{k-1})^n,\qquad \psi_{k,r}=\begin{cases}1&r\equiv0\pmod{k},\\-1&r\equiv1\pmod{k},\\0&\text{otherwise.}\end{cases}$$
- $$\sum_{r=0}^{\min(R,s)}q_rP_{s-r}=\begin{cases}(-1)^{s/k}\binom{n}{s/k},&k\mid s,\\0,&k\nmid s,\end{cases}\qquad q_r=\psi_{k,r}\mathcal{B}(n,k,r),\quad R=(k-1)n$$
- $$j^*(a)=\max\{j\in\{0,\ldots,k-1\}:t_j\le a\},\qquad t_{j^*(a)+1}\leftarrow\min\bigl(t_{j^*(a)+1},a\bigr)$$

## Implementation notes

Integrate the constraint immediately before the transformer output softmax, where each model token is assigned an integer rank a in {0,...,n-1}; for a language model, n can be a rank-bucket count rather than the full vocabulary size. Maintain one tails vector t[1:k-1] per beam or sampled sequence. Pseudocode: initialize t[j]=infinity; at every decoding step, for every candidate rank a compute j=max({0} union {j:t[j]<=a}); mark a invalid when j==k-1; set logits[a]=-infinity for invalid candidates; after selecting a, update t[j+1]=min(t[j+1],a), scanning j from k-1 down to 0 so one token is not reused. For exact uniform constrained-data generation, define C_l(t) as the number of valid length-l suffixes from state t, with C_0(t)=1 and C_{l+1}(t)=sum over valid ranks a of C_l(update(t,a)). Select the next rank with probability C_remaining(update(t,a))/C_{remaining+1}(t). Precompute these values by memoized dynamic programming over tails states. Independently compute the empty-state total P(n,k,s) from the generating-function recurrence using q_r; this checks the state-DP implementation exactly. The mathematics supplies the global count and recurrence, while the state-conditioned suffix counts are computed by the proposed finite-state dynamic program. First test n=16, k in {3,4,5}, and lengths 32-128 using a small GPT-2 or Transformer decoder on synthetic sequences. Compare unconstrained sampling, rejection sampling, and the proposed mask/sampler using validity rate, perplexity, diversity, and downstream accuracy. Success requires 100% validity without rejection blow-up, exact agreement between DP totals and generating-function counts, and improved performance or calibration on a synthetic next-token task whose targets obey the constraint.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.