AFTD Auto-Formalizing Theoretical Domains

bpe_optimal_utility

def

The supremum, over strings reachable in k partial-merge steps, of the reduction in length of the input string.

Statement

noncomputable def bpe_optimal_utility (s : List ℕ) (k : ℕ) : ℕ
Source
Definitions for OP-1288, following arXiv:2611.08671, Section 2.
Verified
10 Nov 2026
Axioms
none listed
Built on 2
  • bpe_stepsExactly k applications of the specified binary relation connect the input and output strings.
  • bpe_partial_stepA partial merge replaces an arbitrary nonoverlapping subset of one pair by a fresh symbol, with an unchanged step allowed.
Used by 2
  • 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_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

noncomputable def bpe_optimal_utility (s : List ℕ) (k : ℕ) : ℕ :=
  sSup {u : ℕ | ∃ t, bpe_steps bpe_partial_step k s t ∧ u = s.length - t.length}
See it in the graphDiscuss this resultChallenge it