AFTD Auto-Formalizing Theoretical Domains

bpe_greedy_step_length_le

theoremverified

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.

  1. 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.

    lines 3–5

    uses bpe_full_merge.induct

      induction s using bpe_full_merge.induct a b with
      | case1 => simp [bpe_full_merge]
      | case2 x => simp [bpe_full_merge]
  2. 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.

    lines 6–9

    uses if_pos, List.length_cons

      | case3 x y xs h ih =>
        rw [bpe_full_merge, if_pos h]
        simp only [List.length_cons]
        omega
  3. The 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`.

    lines 10–12

    uses if_neg

      | case4 x y xs h ih =>
        rw [bpe_full_merge, if_neg h]
        simpa using ih
  4. In 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`).

    lines 16–17

    uses le_rfl

      rcases h with ⟨-, rfl⟩ | ⟨a, b, z, -, -, -, rfl⟩
      · exact le_rfl
  5. 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`.

    line 18

    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

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
See it in the graphDiscuss this resultChallenge it