Tag arrays

Travis Gagie

REVIEW 4 major objections 5 minor 10 references

Tag arrays

T0 review · 4 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper argues that any context-local property of a repetitive text yields a tag array that is run-length compressible, either directly or after a small differential step.

desk verdict A clear, honest position note that overclaims: the central tag-array compressibility assertion is under-specified and contradicted by the paper's own LCP-to-end example, but the phylogenetic conjecture is worth a serious referee. read the letter →

arxiv 2411.15291 v1 pith:AJEW7BPW submitted 2024-11-22 cs.DS

Travis Gagie This is my paper · ORCID

classification cs.DS

keywords tagarrayBurrows-Wheelertransformrun-lengthcompressioncontextuallocalityrepetitivetextpangenomestringattractorsdifferential

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes a general principle: for a repetitive text, any property whose values (tags) tend to agree on characters with similar right-contexts will, when written in Burrows-Wheeler order, consist mostly of runs. This tag array should therefore be run-length compressible, either directly when equal tags cluster or after a simple differential step when neighboring tags are merely close. The paper supports this with known examples such as positions within a repeated copy, LCP and interleaved LCP values, and reports that species tags in pangenomes behave this way; it also conjectures the same for phylogenetic positions. The payoff would be a uniform compressed way to store semantic annotations on repetitive texts.

What carries the argument

The central object is the tag array: the sequence of property values (tags) attached to the text's characters, written in BWT order rather than text order. The mechanism carrying the argument is the BWT's grouping of characters that share the same following context; a property with contextual locality places identical or similar tags into consecutive positions, producing runs. When tags are merely similar rather than identical, the minor manipulation is differential coding of neighboring values, which turns near-equality into runs of small numbers.

What would settle it

Count the runs in a species tag array on a pangenome with many genomes per species: if the run count grows linearly with total text length rather than staying close to the number of species, contextual locality is too weak for the claim to hold on that data.

Watch

Extended reading notes

Core claim

The central claim is that the Burrows-Wheeler Transform turns contextual locality into textual locality. If characters with similar right-contexts tend to carry the same or similar property values, then writing those values in BWT order produces a string, the tag array, with few runs or gently changing neighboring values. The paper argues this should hold for repetitive texts, gives periodic-text and multiple-alignment examples, and points to pangenome species tags as a real instance where it does hold. A final conjecture extends the idea to phylogenetic positions, where tags would be similar but not equal and differential compression would take the place of direct run-length encoding.

Load-bearing premise

The argument rests on the assumption that characters grouped together by their shared following context really have equal or nearly equal tags in the data at hand; if a property violates this, the tag array is no more compressible than the document array.

Editorial extensions

If this is right

For any repetitive text and any context-local property, the tag array can be stored in space proportional to its number of runs, so annotations on repetitive collections become cheap to keep.
Species tags in pangenomes, which the cited metagenomic work already uses, are an instance where contextual locality holds, so the tag array compresses by runs.
The tag array generalizes the document array: with one genome per species the tag array reduces to that familiar structure, and the argument places known compressed representations of the document array inside the same picture.
If the phylogenetic conjecture is right, similar-but-not-equal tags remain compressible after differential coding, offering a route competitive with grammar-compressing document arrays.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A formal version of the claim would need a quantitative definition of similar contexts and similar tags; testing run counts on real alignments is the natural next step.
The same reasoning should apply to left-context properties by reversing the text, or to two-dimensional alignment contexts, extending tag arrays beyond right-context locality.
If tag arrays are as compressible as argued, any per-character annotation such as coverage, quality, or variant status could ride along in a compressed index, not just coordinates and document identifiers.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear colleague,

The short version: this is an informal position note that overclaims. It takes the tag-array idea from Balaz et al. and generalizes it, but the general claim is not defined well enough to be true or false, and the paper's own evidence cuts against it. Still, the phylogenetic conjecture at the end is interesting and testable, and the exposition is clear.

What's actually new: the paper frames "contextual locality" as a unifying property that explains compressibility of several known arrays (document array, SA, LCP, PLCP, ILCP) under BWT order, and it proposes a concrete conjecture about tagging characters with phylogenetic positions when there is one genome per species. That conjecture is the one genuinely new, falsifiable idea here. The historical survey of which arrays have run-like structure in row-major versus column-major order is also useful.

The soft spot is the load-bearing claim in the abstract: that for any repetitive text and contextually local property, the tag array will be run-length compressible "directly or after some minor manipulation." The paper never defines contextual locality formally, never fixes what "minor manipulation" means, and gives no theorem. With an unrestricted transformation class the claim is close to vacuous. The only quantitative evidence offered for the key premise is an in-preparation paper by Depuydt et al., with no data shown. And the paper itself admits that one property that looks contextually local—the LCP measured to the ends of strings—does not scale to real pangenomes. That is a direct counterexample to the abstract's universal claim, at least on the informal definition the paper uses, and the paper doesn't reconcile it. That's a serious consistency problem, not a minor gap.

What the paper does well: it is honest, it flags the LCP failure explicitly, and it keeps the presentation compact. The conjecture about phylogenetically tagged arrays is a good research prompt: it might be true, and it would be interesting if it held. But the note is a position piece, not an established result.

Who's it for: people working on compressed pangenomic indexes who want a conceptual map of why some arrays are BWT-compressible. I'd treat it as a discussion paper, not as a citable theorem. I wouldn't cite it in the next year, but I might bring it to a reading group as a starting point for a more formal treatment.

Recommendation: if this came across my desk, I'd send it to peer review rather than desk-reject it—with a strong request that the author either prove a precise version of the claim (with a formal definition of contextual locality and a quantitative bound) or reframe it as a conjecture/vision paper. The idea deserves a serious referee, but the current draft would need major revision before acceptance.

Referee Report

4 major / 5 minor

Summary. This paper introduces the notion of a tag array: given a text and a property that assigns a tag to each character, the tag array lists the tags of the characters in the order induced by the Burrows-Wheeler Transform (BWT) of the text. A property is said to have contextual locality if characters with similar right-contexts tend to receive the same or similar tags, and the paper argues informally that for repetitive texts every context-local property yields a run-length-compressible tag array, either directly or after 'minor manipulation'. The argument moves by analogy from periodic texts, through the toy alignment of Figures 2 and 3, to a cited pangenomic application in which species tags are placed in BWT order; a final conjecture concerns phylogenetic-position tags and differential compressibility. The manuscript contains no theorems and no formal definitions of contextual locality or 'minor manipulation', and reports no systematic experiments; the one experimental observation it does report is a failure (LCP-to-end-of-string values in BWT order are not run-length compressible on real pangenomic datasets).

Significance. If established precisely, the tag-array viewpoint would be a genuinely useful conceptual link between BWT-run structure and the compressed representation of auxiliary annotations in pangenomics, and the phylogenetic-tag suggestion is a plausible and testable research hypothesis. The paper has real strengths: it is clearly written, its toy examples (Figures 1–3) are instructive, its literature summary (Mantaci et al., the document array, PLCP/LCP, string attractors) is accurate, and it is commendably honest in stating that the LCP-to-end property fails on real pangenomic data and in labeling the phylogenetic proposal as a conjecture. These strengths do not offset the central difficulty: the abstract's categorical claim is neither formalized nor empirically supported, the only real-data instance rests on an in-preparation paper, and the paper's own experimental admission indicates that the periodic intuition does not automatically transfer to the approximately repetitive regime. As submitted, the paper reads as a research note or position statement rather than a paper establishing its main claim.

major comments (4)

[Abstract; opening paragraph] The central claim of the abstract — that a context-locally tagged repetitive text yields a run-length-compressible tag array 'either directly or after some minor manipulation' — is not a formal statement, because 'contextual locality' is never given an operative definition (no threshold relating context similarity to tag equality) and the class of 'minor manipulations' is never specified. With an unbounded transformation class the claim is close to vacuous, since any array can be made run-length compressible by a suitable transformation; the paper needs to fix allowed manipulations, define contextual locality quantitatively, and state a concrete bound on the number of tag-array runs in terms of a measure of the text's repetitiveness (for example, the length of the period in the periodic case, or the number r of BWT runs).
[Paragraph beginning 'Truly periodic strings are common in combinatorics on words'] The paper concedes that the LCP-to-end-of-string property, which has the predicted run-like structure in column-major order in the toy alignment of Figures 2 and 3, 'does not scale to real pangenomic datasets' when the values are placed in BWT order. Since real pangenomes are precisely the approximately periodic regime to which the abstract's claim is meant to apply, this admission directly undermines the generalization from the periodic case, and no other quantitative evidence is offered that column-major run structure survives in approximately repetitive texts.
[Paragraph beginning 'Depuydt et al. [2]'] The only real-data instance of contextual locality supporting the central claim is the species-tag array, and its key premise — that 'nearly all characters have longer shared contexts with corresponding characters in other genomes of the same species' — is asserted without data, code, or a definition of 'longer shared contexts', on the authority of a paper marked 'in preparation'. The step from longer shared contexts to run-length compressibility of the tag array is exactly the nontrivial inference that the manuscript elsewhere shows can fail (for LCP-to-end values), so this premise is load-bearing and currently not independently checkable.
[Definition of contextual locality (abstract; first paragraph)] Because contextual locality is defined only informally as 'characters with similar contexts tend to have the same or similar values', while the BWT is defined to group characters by right-context, the claimed implication from contextual locality to tag-array compressibility holds almost by construction, and the manuscript gives no independent criterion by which the hypothesis could fail for a concrete property. To make the central claim falsifiable, the paper should identify at least one concrete property and text family for which it predicts a specific run-length bound, and say which empirical observations would refute the prediction.

minor comments (5)

[Opening paragraph] The sentence 'the BWT of a periodic text has most as many runs as the length of the period of the original text' appears to contain a typo; it should read 'at most as many runs'.
[Paragraph beginning 'If we measure only to the ends of the copies...'] The parenthetical gloss that equates the LCP a suffix shares with any other suffix with 'the distance from the start of that suffix to the next end of the copy of the repeated substring' is only valid for exactly periodic texts; the wording should be relaxed for the approximately repetitive setting that the paper is actually concerned with.
[Paragraph beginning 'As far as we know, however...'] The claim that the faster version of Li's forward-backward algorithm [8] is 'much simpler and more practical' than Baláz et al.'s approach is an unquantified comparative judgement that is not needed for the paper's argument; the paper should either support the comparison or remove it.
[Final paragraph] The phylogenetic-position scheme is honestly presented as a conjecture, but the abstract's phrase 'directly or after some minor manipulation' should explicitly acknowledge that this conjecture concerns differential compressibility rather than the run-length compressibility promised in the opening sentence; a small pilot experiment on real or simulated pangenomes would materially strengthen the proposal.
[Paragraph beginning 'As far as we know, however...'] The paper's admission that the other contextual-locality properties it surveys are 'probably not of practical interest' leaves the species-tag example as the only practically motivated instance of the central claim; the abstract should reflect that the practical case is currently a single, unverified example.

Circularity Check

2 steps flagged · score 8.0 of 10

The tag-array claim reduces to its own definition: 'contextual locality' is defined by exactly the behavior that makes BWT-order tags run-length compressible, and the only real-data instance is a self-cited in-preparation paper.

self definitional [Abstract, opening definition and thesis]
"We say that a property has contextual locality if characters with similar contexts tend to have the same or similar values (“tags”) of that property. We argue that if we consider a repetitive text and such a property and the tags in their characters’ BWT order, then the resulting string — the text and property’s tag array — will be run-length compressible either directly or after some minor manipulation."

The BWT is defined to group characters with the same or similar right-contexts, so the antecedent “such a property” already contains the consequent: tags are similar for similar contexts, hence in BWT order these tags form runs. The qualifier “tend to” is unquantified and “minor manipulation” is unspecified, so the statement is not a falsifiable theorem but an analytic restatement of the definition. No equation or independent bound connects text repetitiveness to the number of tag-array runs.
self citation load bearing [Paragraph beginning “Depuydt et al. [2]” (pages 3–4)]
"Depuydt et al. [2] use a tag array of pangenomes of several species for metagenomic classification. A character’s tag in this case is the species of the genome containing that character. Since the pangenomes consist of genomes from hundreds to thousands of individuals, nearly all characters have longer shared contexts with corresponding characters in other genomes of the same species than with characters in other species’ genomes. This means the property of “species” has contextual locality and the tag array is run-length compressible."

Reference [2] is “In preparation” and shares an author with this paper, and it is the only place where a concrete property (species) is claimed to satisfy “contextual locality.” The quoted sentence asserts both the premise (“species has contextual locality”) and the conclusion (“the tag array is run-length compressible”) without presenting data, code, or a measurement. Thus the paper’s one real-data instance supports the central claim only through an unverified self-citation chain.

full rationale

The paper’s headline claim is forced by definition: “contextual locality” is defined as the tendency of characters with similar contexts to have similar tags, and the BWT is defined as the ordering that brings characters with similar contexts together. The conclusion that the resulting tag array is run-length compressible is therefore a restatement of the definition rather than an independently derived result. The only concrete application, species tags in pangenomes, rests on a self-cited in-preparation paper with no external evidence, so the empirical half of the claim is also supported by the authors’ own unpublished assertion. The surrounding discussion of LCP, ILCP, suffix array, and string attractors is not circular and cites external work, but it does not rescue the central claim from being definitional. This warrants a score of 8: the result is forced by definition rather than established by a derivation or by independent data.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No physical entities are introduced. The new notions are definitions: "contextual locality" and "tag array". They carry no independent falsifiable handle beyond the compressibility claim itself, which is the assertion under review. The load-bearing assumptions are the empirical locality of species, column, and phylogenetic tags.

assumptions (4)

domain assumption Contextual locality holds for properties such as species and alignment columns: characters with similar contexts tend to have the same or similar tags.
The paper asserts this rather than demonstrates it. It is load-bearing for the metagenomic application and is stated informally in the paragraph citing Depuydt et al.
standard math The BWT groups characters with identical following contexts into contiguous intervals.
This is background from Mantaci et al. [10] and standard BWT theory, used to justify why equal tags form runs.
domain assumption For repetitive texts, shared contexts are long and frequent enough to make tag runs long.
The degree of repetitiveness is not formalized, and the argument depends on long shared contexts to bring tag-similar characters together in BWT order.
ad hoc to paper If there is one genome per species, tagging by left-to-right position in a phylogenetic tree yields similar tags for related species.
Stated in the final paragraph as "it seems likely"; no data or proof is supplied, and this conjecture is needed for the differential-compression claim.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Tag arrays." pith.science (2026). https://pith.science/paper/AJEW7BPW

@misc{pith2026241115291,
  author       = {Pith},
  title        = {Pith review of: Tag arrays},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AJEW7BPW}},
  note         = {Machine review of arXiv:2411.15291}
}

read the original abstract

The Burrows-Wheeler Transform (BWT) moves characters with similar contexts in a text together, where a character's context consists of the characters immediately following it. We say that a property has contextual locality if characters with similar contexts tend to have the same or similar values (``tags'') of that property. We argue that if we consider a repetitive text and such a property and the tags in their characters' BWT order, then the resulting string -- the text and property's {\em tag array} -- will be run-length compressible either directly or after some minor manipulation.

Figures

Figures reproduced from arXiv: 2411.15291 by the authors.

**Figure 2.** A toy alignment (first row, left) and its characters’ column numbers in the alignment (first row, right), its LCP values measuring to the ends of the strings (second row, left), its ILCP values (second row, right), its characters’ row numbers in the alignment (third row, left), its characters’ positions in the concatenation of the strings (third row, right), and the PLCP values for the concatenation of the strings (… view at source ↗

**Figure 3.** The information from Figure 2 but in BWT order inste [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 9 canonical work pages

[1]

Wheeler maps

Andrej Bal´ aˇ z, Travis Gagie, Adri´ an Goga, Simon Heumos, Gonzalo Navarro, Alessia Petes- cia, and Jouni Sir´ en. Wheeler maps. In Proc. Latin American Symposium on Theoretical Informatics, pages 178–192, 2024

work page 2024
[2]

Metagenomic classiﬁcation with tag arrays

Lore Depuydt, Luca Renders, Simon Van de Vyver, Lennart V eys, Travis Gagie, and Jan Fostier. Metagenomic classiﬁcation with tag arrays. In pre paration

work page
[3]

Document retrieval on repet itive string collections

Travis Gagie, Aleksi Hartikainen, Kalle Karhu, Juha K¨ a rkk¨ ainen, Gonzalo Navarro, Si- mon J Puglisi, and Jouni Sir´ en. Document retrieval on repet itive string collections. Infor- mation Retrieval Journal , 20:253–291, 2017

work page 2017
[4]

Fully functional suﬃx trees and optimal text searching in BWT-runs bounded space

Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Fully functional suﬃx trees and optimal text searching in BWT-runs bounded space. Journal of the ACM , 67(1):1–54, 2020

work page 2020
[5]

Permuted longest-common- preﬁx array

Juha K¨ arkk¨ ainen, Giovanni Manzini, and Simon J Puglis i. Permuted longest-common- preﬁx array. In Proc. 20th Symposium on Combinatorial Pattern Matching (CPM) , pages 181–192, 2009

work page 2009
[6]

Resolution of the Bu rrows-Wheeler Transform conjecture

Dominik Kempa and Tomasz Kociumaka. Resolution of the Bu rrows-Wheeler Transform conjecture. In Proc. 61st Symposium on Foundations of Computer Science (FOCS ), pages 1002–1013, 2020

work page 2020
[7]

At the roots of dictiona ry compression: string attrac- tors

Dominik Kempa and Nicola Prezza. At the roots of dictiona ry compression: string attrac- tors. In Proc. 50th Symposium on Theory of Computing (STOC) , pages 827–840, 2018

work page 2018
[8]

BWT construction and search at the terabase scale

Heng Li. Bwt construction and search at the terabase scal e. arXiv preprint 2409.00613 , 2024

work page Pith review arXiv 2024

Show all 10 references

[9]

Storage and retrieval of highly repetitive sequence collections

Veli M¨ akinen, Gonzalo Navarro, Jouni Sir´ en, and Niko V¨ alim¨ aki. Storage and retrieval of highly repetitive sequence collections. Journal of Computational Biology , 17(3):281–308, 2010

2010
[10]

Burrows–Wheeler transform and Sturmian words

Sabrina Mantaci, Antonio Restivo, and Marinella Scior tino. Burrows–Wheeler transform and Sturmian words. Information Processing Letters , 86(5):241–246, 2003. 5

2003

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Wheeler maps

Andrej Bal´ aˇ z, Travis Gagie, Adri´ an Goga, Simon Heumos, Gonzalo Navarro, Alessia Petes- cia, and Jouni Sir´ en. Wheeler maps. In Proc. Latin American Symposium on Theoretical Informatics, pages 178–192, 2024

work page 2024

[2] [2]

Metagenomic classiﬁcation with tag arrays

Lore Depuydt, Luca Renders, Simon Van de Vyver, Lennart V eys, Travis Gagie, and Jan Fostier. Metagenomic classiﬁcation with tag arrays. In pre paration

work page

[3] [3]

Document retrieval on repet itive string collections

Travis Gagie, Aleksi Hartikainen, Kalle Karhu, Juha K¨ a rkk¨ ainen, Gonzalo Navarro, Si- mon J Puglisi, and Jouni Sir´ en. Document retrieval on repet itive string collections. Infor- mation Retrieval Journal , 20:253–291, 2017

work page 2017

[4] [4]

Fully functional suﬃx trees and optimal text searching in BWT-runs bounded space

Travis Gagie, Gonzalo Navarro, and Nicola Prezza. Fully functional suﬃx trees and optimal text searching in BWT-runs bounded space. Journal of the ACM , 67(1):1–54, 2020

work page 2020

[5] [5]

Permuted longest-common- preﬁx array

Juha K¨ arkk¨ ainen, Giovanni Manzini, and Simon J Puglis i. Permuted longest-common- preﬁx array. In Proc. 20th Symposium on Combinatorial Pattern Matching (CPM) , pages 181–192, 2009

work page 2009

[6] [6]

Resolution of the Bu rrows-Wheeler Transform conjecture

Dominik Kempa and Tomasz Kociumaka. Resolution of the Bu rrows-Wheeler Transform conjecture. In Proc. 61st Symposium on Foundations of Computer Science (FOCS ), pages 1002–1013, 2020

work page 2020

[7] [7]

At the roots of dictiona ry compression: string attrac- tors

Dominik Kempa and Nicola Prezza. At the roots of dictiona ry compression: string attrac- tors. In Proc. 50th Symposium on Theory of Computing (STOC) , pages 827–840, 2018

work page 2018

[8] [8]

BWT construction and search at the terabase scale

Heng Li. Bwt construction and search at the terabase scal e. arXiv preprint 2409.00613 , 2024

work page Pith review arXiv 2024