AFTD Auto-Formalizing Theoretical Domains

bpe_steps

def

Exactly k applications of the specified binary relation connect the input and output strings.

Statement

def bpe_steps (R : List ℕ → List ℕ → Prop) : ℕ → List ℕ → List ℕ → Prop
Source
Definitions for OP-1288, following arXiv:2611.08671, Section 2.
Verified
10 Nov 2026
Axioms
none listed
Used by 8
  • 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_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.
  • bpe_optimal_utilityThe supremum, over strings reachable in k partial-merge steps, of the reduction in length of the input string.
  • bpe_optimal_full_utilityThe maximum total reduction in string length achieved by any k-step sequence of full Byte-Pair Encoding merges on s.

Lean source view module on GitHub

def bpe_steps (R : List ℕ → List ℕ → Prop) : ℕ → List ℕ → List ℕ → Prop
  | 0, s, t => s = t
  | k+1, s, t => ∃ u, R s u ∧ bpe_steps R k u t
See it in the graphDiscuss this resultChallenge it