AFTD Auto-Formalizing Theoretical Domains

bpe_worst_ratio

def

For a merge budget k, the infimum of greedy length reduction divided by optimal partial-merge length reduction over finite natural-number strings and all greedy tie-breaking runs with positive optimum.

Statement

noncomputable def bpe_worst_ratio (k : ℕ) : ℝ
Source
Definitions for OP-1288, following arXiv:2611.08671, Section 2.
Verified
10 Nov 2026
Axioms
none listed
Built on 3
  • bpe_stepsExactly k applications of the specified binary relation connect the input and output strings.
  • 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_optimal_utilityThe supremum, over strings reachable in k partial-merge steps, of the reduction in length of the input string.
Used by 1

Lean source view module on GitHub

noncomputable def bpe_worst_ratio (k : ℕ) : ℝ :=
  sInf {r : ℝ | ∃ s t : List ℕ, bpe_steps bpe_greedy_step k s t ∧
    0 < bpe_optimal_utility s k ∧ r = ((s.length - t.length : ℕ) : ℝ) / bpe_optimal_utility s k}
See it in the graphDiscuss this resultChallenge it