acceptodds
Withdrawn from ICLR 2027

TOKENPROBE: What Token Counts Reveal About Black-Box Tokenizers

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Token-count interfaces reveal how many tokens a tokenizer emits, but not necessarily where the token boundaries lie. We construct two byte-level BPE tokenizers that share a reachable vocabulary and agree on the count of every input, yet segment some inputs differently; no number of adaptive count queries can distinguish them. Independent copies yield exponentially many count-equivalent segmentation functions, and a distributional lower bound quantifies the error of any point reconstruction. We then characterize what a transcript does identify: a task output is determined exactly when all consistent tokenizers agree on it. TOKENPROBE operationalizes this characterization through finite-class elimination, driven by standard active-query objectives, and task-specific certification. Exhaustive enumeration verifies the construction on all nonempty strings over of length at most ten. In a fully enumerated family of 24 BPE tokenizers with uniformly weighted targets, identifying the count-response class yields perfect held-out counts, yet a fixed representative correctly segments only of target–input pairs. Segmentation unanimity certifies of pairs without error, and boundary-level certificates still determine of internal byte positions on the remaining pairs. These results establish a sharp separation between estimating token counts and recovering a tokenizer's segmentation behavior.

Primary area:
learning theory
Keywords:
Tokenizer Identifiability, Byte-Pair Encoding, Black-Box Learning

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_384ZOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper shows that token counts does not identify the token boundaries and that one can achieve perfect count prediction but fail at distinguishing between tokenizations.

Critical strengths

The construction showing that two tokenizations may always output the same number of tokens for any string yet have different tokenizations is nice and simple.

Critical weaknesses
  1. The flow of the paper is very inconsistent and reads more like notes rather than a paper with a story. For example, Section 5 introduces partial boundary information but never uses it anywhere else (or at least the connection is not clear from the main body of the paper). Figure 2, Table 1, 2 and 4 do not contribute much to the paper. The writing is very confusing. One could move these floats that do not do much for the paper to the appendix and instead be more careful in the writing, which sorely needs attention. The goal of the paper is to show the separation between counts and tokenizations, but this is not a surprising separation and apart from this separation not much follows from that.
  2. The main object of study of the paper is a very simple toy example: at most 8 tokens, 4 merge rules and an alphabet of 3. The paper mostly sweeps the exponential blow up of performing the experiments under the rug, omitting the time it would take to construct the possible candidates, which there are clearly exponentially many.
  3. It is unclear what the goal of the paper is. Although Theorem 2 is nice and simple, it is unsurprising that such tokenizations exist. My question to the authors is: What are the consequences (empirical or theoretical) of your contributions? Apart from the identifiability results, there is not much depth in what can be learned or used from this. The empirical results are shallow, over toy data, and do not address any practical issues in the field.
Questions for authors

What are the consequences, empirical or theoretical, of your contributions? What does this separation allow or disallow us to do?

What is the intuition behind Eq. 8?

Line 364: what does "least-resolved count class" mean? It states 80.51%, but this is not in the table.

Minor issues (no need to answer during rebuttal):

  1. Line 137: ϵ\epsilon is used here undefined. I assume this is a special identifier for end of string?
  2. The writing is very confusing. For example, lines 145-147: "A finite transcript may leave several of them consistent [consistent with respect to what?] and the members of a single remaining class [remaining from what?] may still disagree on a task that O\mathcal{O} does not identify [what is the definition of identify here?]." The paper uses a lot of qualifiers that add nothing to the text and in fact murks the meaning and goal of the sentence. This is indicative of either fully AI writing or heavy AI writing assistance. I highly encourage the authors to rewrite such sentences, as it distracts and disrupts the narrative flow and makes the paper much harder to follow.
  3. Other examples, Line 177: "Each ambiguous decision is local and has a short witness under segment access; count access discards precisely the information needed to resolve it." The last part of this sentence does not make sense to me. It is not that the count discards the information, but rather that it does not help with distinguishing. The sentence following that also adds absolutely nothing to the text, repeating the exact same statement as the previous one.
  4. Proposition 5 (line 209) is more a definition than a proposition. Is there a reason for this to be stated as a proposition?
  5. Line 255: cell here appears undefined. I suppose the authors mean the set of all tokenizers in AA that are consistent with the oracle's response for query qq (i.e. the numerator in Eq. 8). It would be better to be clear and unambiguous and state this to be what is meant by a cell.
Reviewer_b1n8OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The paper addresses finding token boundaries in tokenized text using an unknown BPE tokenizer. Previous work has addressed retrieving token counts from BPE tokenizers by reverse engineering the tokenizer and finding the vocabulary. However, the authors prove that even using the same vocabulary and with the same token count on every possible input, there can be different token boundaries on some inputs, as they depend on the merge order of the tokenizer used (Theorem 2 in the paper).

To address this challenge, the paper proposes TOKENPROBE, which starts with a set of candidate tokenizers and eliminates those that output a count that differs from the reference count in at least one query. It keeps the surviving tokenizers as consistent ones. If all surviving tokenizers agree on a token boundary, the algorithm marks that token boundary as certified.

Critical strengths

I believe the problem is interesting when it comes to auditing language models' outputs. For example, to falsify the tokenization that the LM provider claims is the generated one, or to falsify the use of a specific LM (to address model substitution).

Critical weaknesses
  • The paper needs a clearer motivation: what is the practical value of finding the token boundaries? For example, retrieving token counts has applications in estimating user usage or verifying user bills, but the additional gain from knowing the exact boundaries is unclear. The introduction very briefly mentions "span alignment" without explaining the application or how boundary recovery would improve it.

  • The fact that tokenizers with different merge order can result in different token boundaries on the same text, while having the same token count, somewhat directly follows from the BPE algorithm. Theorem 2 proves that even when this holds on "every input," the tokenizers might still disagree on the token boundaries. The theorem, however, relies only on two merge rules and does not establish how prevalent this would be in realistic tokenizers with a large number of merge rules.

  • I have some concerns about the applicability of the proposed algorithm. The experiments consider only 4 merge rules, which is far less than realistic tokenizers with vocabularies containing tens of thousands of tokens. In realistic scenarios, how can TokenProbe construct a manageable candidate class? Even if it does, it is unclear how often the candidates would agree on a boundary, so that the algorithm can end up with a certified boundary. Moreover, the correctness of such a potential certified boundary lies in the assumption that the true tokenizer belongs to the initial candidate set, which I find to be a strong assumption.

  • Presentation is not clear; many parts were difficult to follow. For example, see the second paragraph of Section 3, or "Discussion and conclusion" as another example of unclear text.

Questions for authors

Please refer to the section on Weaknesses for more details. The main questions are:

  • What is the motivation behind finding the exact token boundaries?

  • Could you please comment on the practicality of TokenProbe for more realistic tokenizers?

  • Do you think Theorem 2 would still hold using larger vocabularies or merge rules?

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

The paper studies what black-box tokenisers’ token count reveals about their segmentation behaviour. The authors prove, on a ranked based BPE construction, that two tokenisers can have the same final vocabulary and token counts, yet yield different segmentations of the underlying text. They extend the result to 2m2^m count-equivalent tokenisers and derive a lower bound on the segmentation error of any count-only predictor.

The paper proposes a method to certify a downstream output (count, context-fit, boundary) whenever all tokenisers consistent with the observed counts agree on it. They propose TokenProbe: a method that decides which queries to send to the tokeniser in order to efficiently narrow down the consistent tokenisers and check which outputs they agree on.

On an exhaustive experiment over all orders of the merges {ab,bc,ca,aaab, bc, ca, aa} and all probe strings over {a,b,ca, b, c} of length at most 5, TokenProbe always identifies the count class, and on all strings of length 6 to 8 a fixed representative of that class segments 4.6% of instances wrongly, whereas certifying only segmentations on which all consistent tokenisers agree covers 90.64% of instances with no errors.

Critical strengths

The paper provides a nice and clear proof, showing why token counts cannot always identify the boundaries/segmentations of the tokeniser, even in the most favorable assumptions (unlimited adaptive queries, known reachable vocabulary).

The task-specific certification is a strong practical complement to the negative result, instead of guessing a tokeniser, it outputs only what all consistent tokenisers agree on, and still recovers most boundaries even when the full segmentation is undetermined.

The paper is nicely written and is easy to follow, the authors are presenting their approach in a great way.

Critical weaknesses

All experiments are on a toy family (3 letter alphabet, 4 merges, strings ≤\leq 8 bytes). There is no evidence of how much count-boundary ambiguity arises for a real tokeniser on natural text, so the practical relevance of the separation is unknown.

The technical contribution is light. TokenProbe requires a fully enumerated candidate set and offers no way to build one for an unknown tokeniser. None of the obstacles listed in Appendix B (pretokenisation, normalisation, templates, noise) are addressed.

Questions for authors

Could you run experiments over a larger/more realistic tokeniser - e.g. a public BPE of a model - generate the merge order families, and report how many count invariant swaps exist, what fraction of tokens’ boundaries are changed?

Does pretokenisation (regex splitting into words) limit the ambiguity of “abc”-like examples in practice?

I remain positive about the paper and I’m willing to adjust my score during the rebuttal.

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

Related papers

Discussion (0)

Sign in to comment.