AFTD Auto-Formalizing Theoretical Domains

bpe_greedy_step_with

def

A greedy full Byte-Pair Encoding merge step with fresh symbol z: either no adjacent pair occurs with positive count in string s and t = s, or there exists an adjacent pair (a, b) achieving the maximal nonoverlapping pair count bpe_max_pair_count s and t is the result bpe_full_merge a b z s of replacing all nonoverlapping occurrences of (a, b) by z.

Statement

def bpe_greedy_step_with (z : ℕ) (s t : List ℕ) : Prop
Defined in
Sennrich, Haddow, Birch, arXiv:1508.07909; Gage, C Users Journal 1994
Verified
12 Nov 2026
Axioms
none listed
Built on 3
  • 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_pair_countThe number of occurrences of the ordered symbol pair replaced by the left-to-right nonoverlapping full merge.
  • bpe_full_mergeThe string obtained by scanning left to right and replacing every available nonoverlapping occurrence of the selected pair with the given…
Used by 2
  • bpe_greedy_run_length_lower_boundApplying k greedy full BPE merges reduces the string length by at most a factor of 2^k: if bpe_greedy_run k s t, then s.length ≤ 2^k *…
  • bpe_greedy_runThe relation defining a k-step greedy Byte-Pair Encoding run on string s yielding string t: for k = 0 we have s = t, and for k + 1 there…

Read back from the Lean

Given a replacement token z : ℕ and lists of tokens s, t : List ℕ, bpe_greedy_step_with z s t asserts that either: 1. The maximum pair count in s is zero (bpe_max_pair_count s = 0) and t = s; or 2. There exist tokens a, b : ℕ such that: - the maximum pair count in s is strictly positive (0 < bpe_max_pair_count s), - the pair count of (a, b) in s achieves this maximum (bpe_pair_count a b s = bpe_max_pair_count s), and - t equals the list obtained by merging all non-overlapping occurrences of the pair (a, b) into z in s (t = bpe_full_merge a b z s).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- One greedy full BPE merge step replacing a maximal pair with fresh symbol z, or leaving the string unchanged if no pair occurs. -/
def bpe_greedy_step_with (z : ℕ) (s t : List ℕ) : Prop :=
  (bpe_max_pair_count s = 0 ∧ t = s) ∨
  ∃ a b, 0 < bpe_max_pair_count s ∧
    bpe_pair_count a b s = bpe_max_pair_count s ∧
    t = bpe_full_merge a b z s
See it in the graphDiscuss this resultChallenge it