bpe_greedy_step_length_le
Any greedy full byte-pair merge step produces an output string of length at most the input string length.
Statement
theorem bpe_greedy_step_length_le (s t : List ℕ) (h : bpe_greedy_step s t) : t.length ≤ s.length- Source
- arXiv:2611.08671
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- bpe_greedy_stepA greedy full-merge step selects any most frequent adjacent pair and a fresh symbol; a string without adjacent pairs remains unchanged.
- bpe_full_mergeThe string obtained by scanning left to right and replacing every available nonoverlapping occurrence of the selected pair with the given…
- bpe_pair_countThe number of occurrences of the ordered symbol pair replaced by the left-to-right nonoverlapping full merge.
- bpe_max_pair_countThe largest nonoverlapping full-merge pair count among adjacent pairs of the current string, with maximum zero for a string shorter than…
- Used by 1
- bpe_greedy_steps_length_leApplying k greedy full byte-pair merge steps to a string produces an output string of length at most the input string length.
Read back from the Lean
For any two lists of natural numbers $s$ and $t$, if $t$ is obtained from $s$ via a greedy Byte Pair Encoding (BPE) step—meaning either: 1. the maximum pair count in $s$ is $0$ and $t = s$, or 2. there exist natural numbers $a$, $b$, and $z$ such that the maximum pair count in $s$ is strictly positive, the pair $(a, b)$ attains this maximum count in $s$, $z \notin s$, and $t$ is the result of replacing every non-overlapping adjacent occurrence of $[a, b]$ in $s$ with $z$— then the length of $t$ is less than or equal to the length of $s$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof first establishes an auxiliary lemma showing that a full byte-pair merge `bpe_full_merge` never increases the length of any list. This helper lemma proceeds by structural induction on the list tailored to `bpe_full_merge`: empty and singleton lists are unchanged, an adjacent matching pair is replaced by a single token (reducing length by at least 1), and non-matching adjacent elements keep the head intact while recursing on the tail. Finally, for the main theorem `bpe_greedy_step_length_le`, case analysis on the definition of a greedy step shows that either the string is unchanged (giving reflexivity) or it is the result of a full merge, which immediately satisfies the inequality by the helper lemma.
The helper lemma holds for the base cases of empty and single-element lists.
We prove by induction on the list `s` that `bpe_full_merge` never increases length, using the induction principle `bpe_full_merge.induct` tailored to the definition. For the empty list `[]` and singletons `[x]`, `bpe_full_merge` leaves the list unchanged, so the lengths are equal (0 ≤ 0 and 1 ≤ 1 respectively), which `simp` resolves directly from the definition.
uses
bpe_full_merge.inductinduction s using bpe_full_merge.induct a b with | case1 => simp [bpe_full_merge] | case2 x => simp [bpe_full_merge]
The helper lemma holds when the first two elements match the target pair `(a, b)`.
For a list `x :: y :: xs` where `x = a` and `y = b` (hypothesis `h`), `bpe_full_merge` replaces the pair `(x, y)` with the single token `z`, giving `z :: bpe_full_merge a b z xs` by `if_pos`. Rewriting list lengths using `List.length_cons` transforms the goal into `(bpe_full_merge a b z xs).length + 1 ≤ xs.length + 2`. Since the induction hypothesis `ih` gives `(bpe_full_merge a b z xs).length ≤ xs.length`, linear arithmetic via `omega` closes the goal.
uses
if_pos,List.length_cons| case3 x y xs h ih => rw [bpe_full_merge, if_pos h] simp only [List.length_cons] omegaThe helper lemma holds when the first two elements do not match the target pair `(a, b)`.
For a list `x :: y :: xs` where `¬(x = a ∧ y = b)` (hypothesis `h`), `bpe_full_merge` keeps the head `x` and continues on `y :: xs`, yielding `x :: bpe_full_merge a b z (y :: xs)` by `if_neg`. The goal reduces to `(bpe_full_merge a b z (y :: xs)).length + 1 ≤ (y :: xs).length + 1`, which follows directly from the induction hypothesis `ih` on `y :: xs`.
uses
if_neg| case4 x y xs h ih => rw [bpe_full_merge, if_neg h] simpa using ihIn a greedy step where no frequent pair exists, the string is unchanged and the length inequality holds by reflexivity.
We split the hypothesis `bpe_greedy_step s t` into its two disjuncts using `rcases`. In the first case, the maximum pair count in `s` is 0 and `t = s`. The goal `t.length ≤ s.length` becomes `s.length ≤ s.length`, which holds immediately by reflexivity (`le_rfl`).
uses
le_rflrcases h with ⟨-, rfl⟩ | ⟨a, b, z, -, -, -, rfl⟩ · exact le_rfl
In a greedy step where a pair is merged, the length inequality follows from the helper lemma.
In the second case of `bpe_greedy_step`, the list `t` is obtained by fully merging the most frequent pair `(a, b)` into a fresh token `z`, so `t = bpe_full_merge a b z s`. The inequality `t.length ≤ s.length` is then an immediate instance of the helper lemma `bpe_greedy_step_length_le_full_merge`.
uses
bpe_greedy_step_length_le_full_merge· exact bpe_greedy_step_length_le_full_merge a b z s
bpe_full_merge.induct- Induction principle for `bpe_full_merge`: to prove a property for all lists, it suffices to prove it for the empty list `[]`, for singleton lists `[head]`, for `x :: y :: xs` assuming the property for `xs` when `x = a ∧ y = b`, and for `x :: y :: xs` assuming the property for `y :: xs` when `¬(x = a ∧ y = b)`.
if_pos- If a proposition `c` is true, the conditional `if c then t else e` evaluates to `t`.
List.length_cons- The length of a prepended list `(a :: as).length` is `as.length + 1`.
if_neg- If a proposition `c` is false, the conditional `if c then t else e` evaluates to `e`.
le_rfl- Inequality is reflexive: `a ≤ a` for any element `a` in a preorder.
bpe_greedy_step_length_le_full_merge- Fully merging non-overlapping occurrences of the pair `(a, b)` into token `z` in string `s` yields a string of length at most `s.length`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
lemma bpe_greedy_step_length_le_full_merge (a b z : ℕ) (s : List ℕ) : (bpe_full_merge a b z s).length ≤ s.length := by induction s using bpe_full_merge.induct a b with | case1 => simp [bpe_full_merge] | case2 x => simp [bpe_full_merge] | case3 x y xs h ih => rw [bpe_full_merge, if_pos h] simp only [List.length_cons] omega | case4 x y xs h ih => rw [bpe_full_merge, if_neg h] simpa using ih/-- A single greedy BPE merge step never increases the length of the string. -/theorem bpe_greedy_step_length_le (s t : List ℕ) (h : bpe_greedy_step s t) : t.length ≤ s.length := by rcases h with ⟨-, rfl⟩ | ⟨a, b, z, -, -, -, rfl⟩ · exact le_rfl · exact bpe_greedy_step_length_le_full_merge a b z s