bpe_steps_greedy_imp_full_steps
Every string reachable by k steps of greedy Byte-Pair Encoding merges is also reachable by k general full-merge steps.
Statement
theorem bpe_steps_greedy_imp_full_steps (k : ℕ) (s t : List ℕ) (h : bpe_steps bpe_greedy_step k s t) : bpe_steps bpe_full_step k s t- Source
- scout/2611-08671-greedy-byte-pair-encoding-achieves-at-least-0-361-of-the-op.md:59
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- bpe_full_stepA full Byte-Pair Encoding merge step: either the string remains unchanged, or all nonoverlapping occurrences of some pair are replaced…
- 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_stepsExactly k applications of the specified binary relation connect the input and output strings.
- 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…
- bpe_full_mergeThe string obtained by scanning left to right and replacing every available nonoverlapping occurrence of the selected pair with the given…
Read back from the Lean
For every natural number $k$ and all lists of natural numbers $s$ and $t$, if $t$ is reachable from $s$ in $k$ steps of the greedy BPE relation (bpe_greedy_step), then $t$ is reachable from $s$ in $k$ steps of the general BPE relation (bpe_full_step).
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 theorem is proved by induction on the number of steps k. For k = 0, both 0-step relations reduce to equality of the start and end lists. For k + 1 steps, the run splits into an initial greedy step to an intermediate list u and k remaining greedy steps from u to t, which by the induction hypothesis form a k-step full-merge run; the result follows because any greedy step is by definition a valid full-merge step (either the identity or a full merge with a fresh symbol).
The base case k = 0 holds: if s reaches t in 0 greedy steps, then s reaches t in 0 full-merge steps.
We induct on the number of steps k, generalizing s so the inductive hypothesis applies to any intermediate list. When k = 0, the definition of `bpe_steps` simplifies both 0-step relations to list equality s = t, so the hypothesis h : s = t directly proves the goal.
induction k generalizing s with | zero => exact h
In the inductive step k + 1, the goal reduces to showing that the initial greedy step s → u is a valid full-merge step.
A (k + 1)-step greedy run decomposes into a single greedy step from s to an intermediate list u (hypothesis hsu) followed by a k-step greedy run from u to t (hypothesis hut). Applying the induction hypothesis to hut shows that u reaches t in k full-merge steps. Witnessing u as the intermediate list for the full-merge sequence, it remains only to show that bpe_full_step s u holds.
| succ k ih => rcases h with ⟨u, hsu, hut⟩ refine ⟨u, ?_, ih u hut⟩The initial greedy step s → u is a valid full-merge step, completing the inductive step.
By definition of `bpe_greedy_step`, the step s → u is either: (1) a trivial step where no pair can be merged and u = s, which satisfies the left disjunct (s = u) of `bpe_full_step` by reflexivity; or (2) a merge of a most frequent pair (a, b) into a fresh token z ∉ s such that u = bpe_full_merge a b z s, which satisfies the right disjunct of `bpe_full_step`. In both cases, s → u is a valid full-merge step.
rcases hsu with ⟨-, rfl⟩ | ⟨a, b, z, -, -, hz, rfl⟩ · left; rfl · right; exact ⟨a, b, z, hz, rfl⟩
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.
/-- Every k-step greedy Byte-Pair Encoding run is a valid k-step full-merge sequence. -/theorem bpe_steps_greedy_imp_full_steps (k : ℕ) (s t : List ℕ) (h : bpe_steps bpe_greedy_step k s t) : bpe_steps bpe_full_step k s t := by induction k generalizing s with | zero => exact h | succ k ih => rcases h with ⟨u, hsu, hut⟩ refine ⟨u, ?_, ih u hut⟩ rcases hsu with ⟨-, rfl⟩ | ⟨a, b, z, -, -, hz, rfl⟩ · left; rfl · right; exact ⟨a, b, z, hz, rfl⟩