AFTD Auto-Formalizing Theoretical Domains

bpe_greedy_step

def

A greedy full-merge step selects any most frequent adjacent pair and a fresh symbol; a string without adjacent pairs remains unchanged.

Statement

def bpe_greedy_step (s t : List ℕ) : Prop
Source
Definitions for OP-1288, following arXiv:2611.08671, Section 2.
Verified
10 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 7
  • bpe_min_greedy_utility_one_eq_optimalFor any string s and merge budget k = 1, the minimum reduction in length achieved by a greedy full-merge step equals the optimal reduction…
  • bpe_worst_ratioFor a merge budget k, the infimum of greedy length reduction divided by optimal partial-merge length reduction over finite natural-number…
  • 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.
  • bpe_min_greedy_utilityThe minimum total reduction in string length achieved by any k-step greedy Byte-Pair Encoding merge run on s under arbitrary tie-breaking.
  • bpe_steps_greedy_imp_full_stepsEvery string reachable by k steps of greedy Byte-Pair Encoding merges is also reachable by k general full-merge steps.
  • bpe_greedy_step_length_leAny greedy full byte-pair merge step produces an output string of length at most the input string length.
  • bpe_worst_case_ratio_three_upper_boundThe worst-case ratio of greedy Byte-Pair Encoding to optimal partial-merge utility for three merges is at most 7/12.

Lean source view module on GitHub

def bpe_greedy_step (s t : List ℕ) : Prop :=
  (bpe_max_pair_count s = 0 ∧ t = s) ∨
  ∃ a b z, 0 < bpe_max_pair_count s ∧ bpe_pair_count a b s = bpe_max_pair_count s ∧
    z ∉ s ∧ t = bpe_full_merge a b z s
See it in the graphDiscuss this resultChallenge it