acceptodds
Under review as a conference paper at ICLR 2027

Pair Encoding: Approximation and the Cost of a Strict Budget

Abstract

How well can pair encoding compress a string with a limited number of merge rules? We characterize legal partial executions as reachable creation-ordered binary forests and establish a separation between strict and relaxed budgets. For every string, we construct one binary hierarchy whose prunings approximate both the rule count and final length of every comparison forest within . This yields a uniform weighted approximation and an unconditional budget/length bicriteria algorithm. Conversely, unless , no deterministic polynomial-time algorithm achieves a sublinear length factor under a strict budget on growing-alphabet inputs, even with sufficiently small fixed budget inflation and complete freedom to redesign the dictionary. The hardness is witnessed by an NP-hard gap between one final token and linearly many tokens; extracting a vertex cover from any output forest makes the conclusion independent of dictionary design. The rule-free -approximation has the optimal worst-case asymptotic order at strict budget. We also derive computable length certificates and sharp utility-loss identities across snapshot, final-state, and temporal resolutions. Reproducible experiments retain all exact records and full-window runs, measuring certificate strength, policy sensitivity, and the structural identities on finite inputs.

Primary area:
learning theory
Keywords:
tokenization, pair encoding, byte pair encoding, string compression, approximation algorithms, bicriteria approximation, hardness of approximation, straight-line grammars, computational complexity

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_rTFoOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the computational complexity of compressing a single string via merges of pair-enconded rules. More precisely, a rule has the form X>YZ, where X is a new unused symbol (Y and Z are symbols too) and replaces at least one occurrence of YZ by X (not necessarily all). The goal is to minimize the total number L of tokens (total length of the resulting string) using at most k rules. The main results of the paper are as follows:

  1. If the budget k has to be respected exactly then unless P=NP, no deterministic polynomial-time algorithm can guarantee in the worst case a length that is more than a constant factor better than doing nothing. This result is shown by a reduction from cubic vertex cover.
  2. If more than k rules are allowed, then a simple hierarchy gets a O(log^2 n) approximation. Moreover, experiments on small stings are conducted.

JUDGMENT

The results are interesting, but did not check the proofs in detail. I only checked there main ideas which seem to be correct to me. My main concerns are the limited technical novelty and the limited interest for the ML community. Another downside is the current presentation which contains many undefined notation. Thus, I think the paper does not meet the bar for acceptance at ICLR.

Critical strengths
  1. The paper uses nice connections between pair encodings and tools of grammar compression.

  2. The positive algorithmic results is non-trivial

  3. the provided lower bound is computable in polynomial time and is often tight in small instances

  4. The shown hardness result holds in quite restricted settings

Critical weaknesses
  1. The hardness result is very close to existing work. Moreover, the budget k is very large (linear) in the reduction, so the result has no implications for small k. In general many results are close to existing results.

  2. The experiments do not verify any of the main results. Also the tested string length is very small.

  3. I don't think the studied problem is broadly relevant for an ML audience. Also the citations show this: most of them are string-conferences and TCS conferences.

  4. I think since the problem is quite related to the smallest grammar problem, more papers on this problem should be cited, for example: 'On the Complexity of Grammar-Based Compression over Fixed Alphabets' to name one. (i did a quick scholar search for this)

  5. It was quote hard for me to follow this paper: Already the overview paragraph in Line 43 is hard to follow for someone outside of the area. Also, many notations are used, before they are defined (or are never defined). For me, Algorithm 1 was only understandable with the appendix. Also OPE is never explained and token is only explained in the appendix.

Questions for authors
  1. What do OPE, OMS and WPF stand for?

  2. Can you give an intuition for the values of q, \rho_n and \beta_n (line 211) and for the certificate quantities A_\partial(s) and LB_\partial(s,k) (line 337)?

  3. Why did you not evaluate your algorithm? And why were only very small instances tested?

  4. Can the hardness result be strengthened, for example to constant size alphabets or sublinear budgets?

Further Comments:

  • Some abbreviations are never expanded: OPE, OMS, WPF, BPE, SLP, EvenOdd, SLP, q-gram

  • the notion of a token is defined only in Appendix A, but the main text uses 'final tokens' (also applies to snapshot)

  • used before the definition: n, U, L*, WPF_\lambda, \lambda, \rho_n, \beta_n, p_m(s), m, A_\partial, LB_\partial

  • line 591: suf_a(.) and pre_{m-a}(.) are not defined

  • the paragraph starting in line 43 is hard to follow for me as a reader outside the area: it uses notions that are not yet defined (dependency-closed pruning, comparison grammar, rule/root pair, L*), and in the inequalities r <= O(log^2 n)k and L <= O(log^2 n)L*(s,k) it is not said to which object r and L refer

  • line 47: the 'trivial n-approximation' is not explained at this point

  • line 211: please give an intuition for q, \rho_n and \beta_n.

  • paragraph starting in line 296: instead of listing the normalization steps, it would be more helpful to explain the concrete correspondence between forests and vertex covers

  • line 337: please provide an intuition for A_\partial(s) and LB_\partial(s,k)

  • line 681: 'but not length membership in APX' is a strange formulation. Please reformulate, for example: 'but it does not show that the length version is in APX'

  • line 549 / Section 2: the model seems to allow a later rule X' -> ab with a fresh label but the same right-hand side as an earlier rule X -> ab. This is never beneficial and I think the paper uses this implicitly

Reviewer_nSwBOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the algorithm and hardness of pair encoding, a string processing problem relevant to tokenization in modern LLMs: Given a string ss of length nn and a budget of kk merging rules, how small can we make the length of the merged string LL? The paper approaches this problem from a theoretical point of view; prior work also studied this problem and gave theoretical results. Overall, the research question is natural and interesting.

The results are twofold:

  • On the positive side, Algorithm 1, on input (s,k)(s, k), outputs a "host solution" HH with the following approximation guarantee: for any feasible solution FF, a pruning of HH yields a solution H′H' that (1) uses at most O(log⁡2n)kO(\log^2 n) k rules and (2) L(H′)≤O(log⁡n)L(F)L(H') \leq O(\log n) L(F).
  • On the negative side, assuming P≠NP\mathbf{P\ne NP}, no deterministic polynomial-time algorithm can guarantee an approximation factor better than linear in nn, while always respecting the rule budget. This result assumes that the alphabet size can grow with input length.
Critical strengths
  • The universal hierarchy offers a meaningful theoretical advance. Theorem 4.2 uses one host hierarchy, independent of the requested budget or weight, to control rule count and final length separately across all comparison forests. This differs substantively from approximating a single grammar-size objective. The multiplicity-based pruning result also provides an elegant way to optimize within the constructed host.

  • The hardness result is stronger than previous results. Earlier work established APX-hardness and a linear bad-case length ratio for BPE itself. This paper rules out sublinear length approximation for every deterministic polynomial-time algorithm satisfying the budget guarantee. Moreover, growing alphabets were already used in the earlier hardness proofs; the new conclusion is therefore not obtained merely by weakening that assumption (Kozma and Voderholzer, ESA 2026).

Critical weaknesses
  • The techniques for proving the hardness result are already present in previous results, making the result incremental.

  • The hardness result requires a growing alphabet. If one can prove hardness of approximation in the fixed alphabet setting, that would be more interesting.

  • This writing could benefit greatly from further revision. For example, the description of Algorithm 1 is difficult for a first-time reader to grasp.

Questions for authors
  • As far as I understand, the results are theoretical. What is the meaning of the experiments?

  • Is there any connection to practical tokenization? Anyway, I do agree that the question studied is theoretically interesting.

Reviewer_WjrgOpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
1
Soundness
3
Read review
Paper summary

The paper studies the approximation complexity of optimal pair encoding under a limited set of merge rules. It establishes an equivalence between the partial merges and binary forests, and constructs a O(log⁡2n)O(\log^2n) approximation for both the rule budget and final sequence length.

It also proves that, for growing alphabets, no deterministic polynomial time algorithm can achieve a sublinear length approximation under a strict budget, unless P=NP. Additional contributions include computable lower bounds and structural results about compression utility, supported by theoretical proofs and finite experiments.

Critical strengths

The paper proves an O(log⁡2n)O(\log^2n) bicriteria approximation for the number of merge rules and final sequence length.

The paper establishes a strong hardness result, showing that, for growing alphabets, no polynomial-time algorithm can achieve a sublinear length approximation under a strict rule budget.

Critical weaknesses

The paper is difficult to follow due to its dense presentation and numerous auxiliary results, which often obscure the main contributions.

The proposed approximation algorithm is not evaluated experimentally, making its practical performance compared to existing methods unclear.

Questions for authors

The hardness result only applies to growing alphabets. Do the authors expect a similar result for fixed alphabets, which are of more practical relevance?

I found the main proofs difficult to follow, especially with many details spread across the appendices. Could the authors provide more intuitive explanations of the two main results and shorten some of the less central material? I'm willing to increase my score upon improvements of the manuscript.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Discussion summary

We thank the AC and all three reviewers for their time and careful reviews.

In short, the revision makes the paper easier to read, adds proof ideas for both main results, adds an experiment comparing our algorithm with BPE, explains why the hardness proof needs a growing alphabet and a linear budget, and credits earlier work more clearly. No theorem or proof changed in substance. The full list of changes is in our general comment of 7 Nov.

Thank you all again for your time and helpful comments.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.