AFTD Auto-Formalizing Theoretical Domains

bpe_lex_run

deforiginal

The string obtained by performing k sequential greedy lexicographical full BPE merges on an initial string over symbols 0 and 1.

Statement

def bpe_lex_run : ℕ → List ℕ → List ℕ
Related work
knowledgebase
Verified
11 Nov 2026
Axioms
none listed
Built on 1
  • bpe_lex_stepPerforms one greedy full BPE merge step replacing the chosen lexicographically earliest maximal pair with fresh symbol z, leaving the…
Used by 1
  • bpe_densityFor natural numbers k and N and sequence w : Fin N → ℕ, the real token density bpe_density k N w is the length in ℝ of the list obtained…

Read back from the Lean

A recursive definition bpe_lex_run : ℕ → List ℕ → List ℕ that performs k iterations of a deterministic Byte Pair Encoding (BPE) merge on a list of natural numbers s: - At 0 iterations, it returns the input list s unchanged. - At k + 1 iterations, it computes the intermediate list s' := bpe_lex_run k s, and then applies one merge step (bpe_lex_step) to s' using the token identifier k + 2. In that merge step: 1. It inspects all adjacent pairs in s'. If s' has length < 2, no pair exists and s' is returned unchanged. 2. If adjacent pairs exist, it selects the "best" pair (a, b): the adjacent pair maximizing the non-overlapping occurrence count in s', breaking ties by choosing the lexicographically smallest pair (smaller first component, then smaller second component). 3. It performs a greedy left-to-right replacement of all non-overlapping occurrences of [a, b] in s' with the single natural number k + 2.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Performs k greedy full BPE merges with fresh symbol IDs 2, 3, ..., k + 1. -/
def bpe_lex_run : ℕ → List ℕ → List ℕ
| 0, s => s
| k + 1, s => bpe_lex_step (k + 2) (bpe_lex_run k s)
See it in the graphDiscuss this resultChallenge it