AFTD Auto-Formalizing Theoretical Domains

bpe_greedy_steps_length_le

theoremverified

Applying k greedy full byte-pair merge steps to a string produces an output string of length at most the input string length.

Statement

theorem bpe_greedy_steps_length_le (k : ℕ) (s t : List ℕ) (h : bpe_steps bpe_greedy_step k s t) : t.length ≤ s.length
Source
arXiv:2611.08671
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • bpe_stepsExactly k applications of the specified binary relation connect the input and output strings.
  • 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_greedy_step_length_leAny greedy full byte-pair merge step produces an output string of length at most the input string length.

Read back from the Lean

For all natural numbers $k$ and all lists of natural numbers $s$ and $t$, if $t$ can be reached from $s$ in $k$ steps of the greedy Byte Pair Encoding relation (bpe_greedy_step), 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 proceeds by induction on the number of steps $k$, generalizing over the initial string $s$. In the base case $k = 0$, taking zero merge steps leaves the string unchanged ($s = t$), so the lengths are trivially equal. In the inductive step $k + 1$, the sequence decomposes into an initial greedy step $s \to u$ followed by $k$ steps $u \to^* t$; chaining the single-step bound $|u| \le |s|$ with the induction hypothesis $|t| \le |u|$ via transitivity of $\le$ completes the proof.

  1. For the base case $k = 0$, $t.\text{length} \le s.\text{length}$ holds.

    We proceed by induction on $k$, generalizing over the initial string $s$. In the base case $k = 0$, simplifying hypothesis $h$ with the definition of `bpe_steps` yields $s = t$. Substituting $t$ with $s$, the goal becomes $s.\text{length} \le s.\text{length}$, which holds by reflexivity of $\le$ (`le_rfl`).

    lines 3–7

    uses le_rfl

      induction k generalizing s with
      | zero =>
        simp only [bpe_steps] at h
        subst h
        exact le_rfl
  2. In the inductive step $k + 1$, $t.\text{length} \le s.\text{length}$ holds.

    For the inductive step $k + 1$, the hypothesis that $s$ reaches $t$ in $k + 1$ steps means, by definition of `bpe_steps`, that there is an intermediate string $u$ such that $s$ takes one greedy step to $u$ and $u$ takes $k$ greedy steps to $t$. By `bpe_greedy_step_length_le`, the first step does not increase length ($u.\text{length} \le s.\text{length}$). By the induction hypothesis applied to $u$, the remaining $k$ steps satisfy $t.\text{length} \le u.\text{length}$. Chaining these two inequalities via transitivity of $\le$ (`le_trans`) completes the step.

    lines 8–12

    uses bpe_greedy_step_length_le, le_trans

      | succ k ih =>
        obtain ⟨u, hsu, hut⟩ := h
        have h1 := bpe_greedy_step_length_le s u hsu
        have h2 := ih u hut
        exact le_trans h2 h1
le_rfl
Inequality in any preorder is reflexive: $a \le a$ for any $a$.
bpe_greedy_step_length_le
A single greedy byte-pair merge step never increases the length of the string: if $s$ steps to $t$, then $t.\text{length} \le s.\text{length}$.
le_trans
Inequality in any preorder is transitive: if $a \le b$ and $b \le c$, then $a \le c$.

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

/-- Any sequence of k greedy BPE merge steps produces an output string of length at most the initial string length. -/theorem bpe_greedy_steps_length_le (k : ℕ) (s t : List ℕ) (h : bpe_steps bpe_greedy_step k s t) : t.length ≤ s.length := by  induction k generalizing s with  | zero =>    simp only [bpe_steps] at h    subst h    exact le_rfl  | succ k ih =>    obtain ⟨u, hsu, hut⟩ := h    have h1 := bpe_greedy_step_length_le s u hsu    have h2 := ih u hut    exact le_trans h2 h1
See it in the graphDiscuss this resultChallenge it