4 papers
Greedy+Singleton for knapsack-constrained monotone submodular maximization has approximation ratio exactly
Kundan Baliga, Aiden Xie, Aditya Byju
Greedy+Singleton is the textbook heuristic for monotone submodular maximization under a knapsack constraint: it returns the better of the cost-benefit greedy set and the best singl…
Pair-Merge Tokenisation Is Hard to Approximate on Binary Strings and Strongly NP-Hard on Unary Datasets
Kundan Baliga, Aiden Xie, Aditya Byju
Tokenisers such as Byte-Pair Encoding (BPE) shorten text by repeatedly merging an adjacent pair of symbols into a new one; fewer tokens mean less computation. We ask whether an eff…
Greedy Byte-Pair Encoding Achieves 0.391 of the Optimum, Past the One-Third Barrier for Packing-Based Analyses
Kundan Baliga, Aiden Xie, Aditya Byju
Byte-Pair Encoding (BPE) builds most language-model tokenisers by repeatedly merging a most frequent adjacent pair of symbols. How much shortening can this greedy rule lose against…
GreedTok Is a 0.3287-Approximation for Tokenization, Within 3% of the Best Possible Constant
Kundan Baliga, Aiden Xie, Aditya Byju
A tokenizer's vocabulary is chosen once and used on every input, so it matters how much compression a greedy vocabulary can lose. GreedTok (Lim et al., 2025) picks tokens one a…