AFTD Auto-Formalizing Theoretical Domains

bpe_steps_greedy_imp_full_steps

theoremverified

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

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

    lines 3–4

      induction k generalizing s with
      | zero => exact h
  2. 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.

    lines 5–7

      | succ k ih =>
        rcases h with ⟨u, hsu, hut⟩
        refine ⟨u, ?_, ih u hut⟩
  3. 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.

    lines 8–10

        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

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