{"id":"7c485b95-5a3c-4e4b-8e89-9a7af50131fa","arxiv_id":"2505.11693","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper derives an optimal hierarchical bracketing encoding for projective dependency trees that uses 12 labels, and extends it to non-projective trees with indexed brackets.","lead":"This paper introduces a family of dependency tree encodings that use fewer distinct labels (12 instead of 16) by marking only some arcs as structural and hanging the rest off them. The new encoding is competitive in accuracy with existing parsing-as-tagging methods and is faster at inference.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's proof assumes a node cannot head both a leftward and a rightward structural arc; the proper rope cover definition does not rule this out, so the 12-label bound is unproven.","rationale":"The reader's weakest assumption identifies exactly the unproven property that a node cannot be the head of both a leftward and a rightward structural arc in a proper rope cover. My analysis confirms this is the load-bearing gap in Theorem 3 and strengthens it: the property is not merely unproven, it is contradicted by the paper's own definitions. Two arcs that share a head but go in opposite directions have disjoint spans apart from the shared endpoint, so neither covers the other, and the definition of 'leans on' does not apply. The greedy proper-rope-cover algorithm can select both such arcs as structural, as demonstrated by a four-word projective tree. If this example encodes as predicted, the 12-label claim fails. Because the notation for superlative vs semibrackets is ambiguous in the text, I frame this as a concrete test rather than a definitive refutation, but the proof as written is invalid. This matches the reader's CONDITIONAL verdict: the paper should not be accepted until Theorem 3 is either proved with the missing argument or corrected to a true bound. The non-projective coverage claim in Section 4 is also asserted without formal proof, but the 12-label theorem is the more central and more clearly problematic claim.","tokens_in":22300,"tokens_out":26140,"duration_ms":242921,"concrete_test":"Enumerate all projective dependency trees with up to n=8 nodes (root 0 included), compute the proper rope cover using the algorithm in Section 3.5, and collect the distinct hierarchical bracketing labels. If any tree produces a label outside the claimed 12, or if the specific tree V={0,1,2,3,4}, E={(0,4),(0,2),(2,1),(2,3)} yields a node-2 label containing both an opening-left and an opening-right superbracket after decoding, then Theorem 3 is false. Even simpler: run the encoding on this single tree and verify whether the number of distinct labels in the output exceeds the 12-label bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 3, Section 3.5) is that the proper rope cover induces a projective encoding using at most 12 labels, because the labels , \\/ cannot occur. The proof asserts that the two structural arcs in such a label would necessarily lean on each other, which is forbidden in a proper rope cover. This assertion is the load-bearing step, and it appears false under the paper's own definitions. An arc (i,j) supports (k,l) only if (i,j) covers (k,l) and they share a left or right endpoint. Two structural arcs with the same head, one going left and one going right — say (i,k) with k < i and (i,j) with j > i — share node i, but the interval [k,i] is not covered by [i,j] and vice versa. They do not lean on each other, so a proper rope cover can contain both. The greedy construction in Section 3.5 does not prevent this: after the longest arc with the leftmost left endpoint is chosen, a remaining leftward and a remaining rightward arc out of the same node can each be selected in later iterations. As a concrete example, the projective tree on V={0,1,2,3,4} with edges (0,4), (0,2), (2,1), (2,3) has, according to the stated algorithm, the proper rope cover {(0,4), (2,1), (2,3)}: (2,1) does not lean on (0,4) because it shares no endpoint, and (2,3) is disjoint from (2,1). Node 2 is then the head of both a leftward and a rightward structural arc, producing a label containing both an opening-left and an opening-right superbracket (together with the parent-closing bracket). This label is not among the four that the proof tries to exclude, and if such a label is possible, the label alphabet exceeds 12. The proof of Theorem 3 therefore lacks the crucial missing argument, and the paper's own definitions suggest the argument cannot be supplied.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces hierarchical bracketing encodings for dependency parsing as sequence labeling, built on the rope-cover framework of Yli-Jyrä. It claims that the existing 4-bit encoding is an instance of this framework, that the proper rope cover induces an optimal (minimum-bracket) encoding, that this encoding uses at most 12 distinct labels for projective trees (versus 16 for the 4-bit encoding), and that an indexed-bracket extension supports arbitrary non-projective graphs. Experiments on PTB and nine UD treebanks report LAS/LCM accuracy roughly on par with previous encodings and improved inference speed.","tokens_in":22666,"tokens_out":29831,"duration_ms":274290,"significance":"The 12-label bound over the 4-bit encoding's 16 labels is the paper's headline theoretical contribution; the non-projective extension and the unifying framework are also of interest. The paper is commendable for providing code and a broad multilingual experimental comparison. However, Theorem 3, which establishes the 12-label bound, is false under the paper's own definitions. This is a load-bearing error: the abstract and introduction advertise a result that the manuscript does not deliver. The remaining contributions are not sufficient to support the paper's conclusions as stated.","major_comments":[{"comment":"The proof of Theorem 3 asserts that labels , \\/ cannot appear because the structural arcs involved would lean on each other, which is forbidden in a proper rope cover. This argument assumes that the < and > symbols in these labels are superbrackets denoting structural arcs. But in the proposed encoding, < and > can also be semibrackets denoting auxiliary arcs, and auxiliary arcs are allowed to lean on structural arcs. A concrete counterexample is the projective tree on V={0,1,2,3,4} with edges (0,4), (0,2), (2,1), and (2,3). Following the algorithm in Section 3.5, the proper rope cover is {(0,4), (2,1), (2,3)}: (0,4) covers (2,1) and (2,3) but shares no endpoint with them, so neither leans on it, and (2,1) and (2,3) do not cover each other. The encoding gives node 2 the label \\>/ (the \\ from structural arc 2->1, the > from the auxiliary arc 0->2, and the / from structural arc 2->3), one of the labels declared impossible. Thus the 12-label bound in Theorem 3 is false, and the central claim of the paper is unsupported.","section":"Section 3.5, Theorem 3"},{"comment":"The text states that the indexed-bracket extensions 'are sufficient to support every non-projective graph,' but no proof of coverage or of the bijectivity of the encoding/decoding is provided. Algorithm 2 is intricate, with indexed semibrackets and superbrackets that skip stack elements, and correctness depends on subtle stack manipulations. Without a formal theorem (or a precise citation of a theorem from Yli-Jyrä 2019b that exactly covers this encoding), the claim of arbitrary non-projectivity support is not established. The complexity bound O(|A| imax^2) in Appendix A.1 is also stated without a derivation.","section":"Section 4, non-projective extension"},{"comment":"All experimental results are reported for a single run, with no variance estimates or significance tests. Many differences between encodings are small, for example en: OP 92.00 vs B4 91.99 LAS, and wo: OP 70.25 vs B4 73.67 LAS, so the conclusion that the proposed encodings are 'competitive' is not statistically supported. Additionally, Table 2 reports exactly 12 generated labels for OP on every treebank; in light of the counterexample to Theorem 3, the authors should explain what algorithm actually produces these labels, since the proper rope cover as defined can require the label \\>/ on some projective trees.","section":"Section 5, Table 3"}],"minor_comments":[{"comment":"In the PTB results table, the H+ row reports '04.80' for test LAS; this appears to be a typo for '94.80'.","section":"Appendix, Table 4"},{"comment":"The pseudocode uses the same glyphs for superbrackets and semibrackets (e.g., '>' appears in both the semibracket branch and the superbracket branch), which makes the algorithm ambiguous as printed. Distinct symbols or an explicit type annotation would improve reproducibility.","section":"Algorithm 1"},{"comment":"The sentence 'For each leftward arc w_i← w_j∈ R, we add an opening superbracket < to the label of w_i and a closing superbracket \\ to the label of w_j' contradicts the convention used elsewhere in the paper (head gets \\, dependent gets <), as confirmed by Figure 1b. This inconsistency should be fixed.","section":"Section 3.2, encoding rules"},{"comment":"The transformation proof of Theorem 2 is sketched rather tersely; in particular, it is not shown explicitly that the replacement arc covers all arcs with left endpoint e_l that previously leaned on r_1, nor that the process terminates in a proper cover rather than a different non-proper fixed point.","section":"Section 3.5, Theorem 2 proof"}],"recommendation":"reject","confidential_remarks":"The counterexample to Theorem 3 is simple, uses the paper's own definitions, and directly defeats the advertised 12-label result. The main theoretical contribution of the manuscript is therefore unsound. Unless the authors can meaningfully redefine the proper rope cover or the encoding so that the 12-label claim holds without abandoning the optimality theorem, this is not fixable within a minor revision. The experimental and framework contributions exist, but they do not compensate for the false central claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper has a genuinely useful framework and a plausible optimality theorem, but the headline 12-label claim rests on a proof step that is simply false. Don't let the paper go through without fixing that.\n\nWhat's new and good: the hierarchical bracketing framework cleanly recasts bracketing encodings as choosing a rope cover, and the 4-bit encoding falls out as a special case. Theorem 2, that the proper rope cover has minimum cardinality, appears solid from the transform argument. The indexed-bracket extension for non-projectivity is a clever way to handle crossing arcs. The empirical work is thorough: ten treebanks, code and data released, and the efficiency comparison is useful. Accuracy is on par with baselines; the real wins are the smaller label set and speed.\n\nSoft spots: Theorem 3 is not proven. The proof says labels containing both a left and right opening superbracket (`` for the incoming auxiliary arc). So the 12-label bound is not established; in fact the example suggests a label outside the 16 the paper's own Theorem 1 would predict. This needs either a fix or a qualification. Also, the claim that the indexed brackets cover every non-projective graph is asserted without proof. And the accuracy tables have no variance estimates; differences between encodings are within a few tenths, so the \"competitive\" claim is fine, but the paper shouldn't over-read those numbers.\n\nThe citation pattern is fine; the dependence on Yli-Jyrä's rope cover is explicit and the adaptation is substantive.\n\nWho this is for: anyone working on parsing-as-tagging or compact tree linearizations. It deserves a serious referee, but with the expectation of a major revision on the theory. I'd recommend accepting it conditionally, with a complete proof of Theorem 3 (or an adjusted claim) and a proof or explicit limitation for the non-projective coverage.","headline":"The hierarchical bracketing framework and the minimum-cardinality theorem are solid, but the headline 12-label claim is not actually proven, and the paper will need a substantive revision before it is publishable as a theory paper.","tokens_in":23238,"tokens_out":20210,"would_cite":true,"duration_ms":187717,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper derives an optimal hierarchical bracketing encoding that represents any projective dependency tree with 12 labels instead of 16, and extends it to non-projective trees.","keywords":["dependency parsing","sequence labeling","hierarchical bracketing","rope cover","projective trees","non-projective trees","tagging-based parsing","compact encodings"],"falsifier":"Find, or computationally search for, a projective dependency tree whose proper rope cover makes the same node the head of both a leftward and a rightward structural arc; such a tree would force one of the four excluded labels and falsify the 12-label theorem. A brute-force check of all small projective trees with the published greedy rope-cover algorithm settles the question.","tokens_in":22115,"feed_emoji":"🏷️","tokens_out":9288,"duration_ms":81361,"temperature":0.7,"pith_summary":"Dependency parsing can be cast as tagging: each word receives a label that encodes where its dependency arcs attach. This paper defines a family of such label schemes, hierarchical bracketing encodings, in which a few arcs are marked as structural with a pair of brackets and all other arcs are written with a single symbol because they lean on a structural arc. The paper proves the established 4-bit encoding is a member of this family but is not the most compact, and derives the optimal member, which encodes every projective tree with 12 distinct labels instead of 16. The same framework is extended to non-projective trees by adding indices to brackets so they can skip other brackets when matching. The payoff is a smaller label vocabulary for the tagger that keeps accuracy competitive across ten treebanks while running faster than earlier fixed-size bracket encodings.","feed_headline":"One encoding change cuts dependency-tag labels from 16 to 12","feed_subtitle":"The optimal bracket scheme also handles non-projective trees and runs faster on English.","key_machinery":"The rope cover is the central object: a subset of arcs chosen as structural so that every other arc leans on one of them, meaning it shares an endpoint with and is covered by a structural arc. Structural arcs are written with two superbrackets, while auxiliary arcs need only one semibracket placed at the endpoint not shared with the supporting arc. The proper rope cover, built by repeatedly marking the longest unmarked arc with the leftmost left endpoint and then marking all arcs that lean on it, is unique and has minimum cardinality, so it minimizes total brackets. In projective trees this construction produces labels whose form is bounded by a regular pattern, giving at most 16 labels for compact covers, and the optimal version rules out four of those labels, leaving 12. The non-projective extension adds numeric indices to brackets so they can skip a specified number of superbrackets when matching, with rope thickness bounding how large the index can be.","core_discovery":"The central claim is that a minimal rope cover, called the proper rope cover, induces an optimal hierarchical bracketing encoding: it uses the fewest structural arcs, hence the fewest bracket symbols, of any hierarchical bracketing of the same tree. For projective trees, the paper proves the label set drops from 16 to 12. Among the sixteen labels a compact hierarchical bracketing can produce, four combine a leftward structural arc with a rightward structural arc at the same node, and the paper argues these cannot occur under the proper rope cover. It also shows the 4-bit encoding is exactly the hierarchical bracketing induced by a different, larger rope cover, which explains why it needs the extra four labels. For non-projective trees, the paper adds indices to closing brackets so that an indexed bracket skips over intervening superbrackets, and reports that index 2 covers every treebank tested except Ancient Greek.","pith_inferences":["If the unproven premise behind the 12-label theorem fails, the bound could become 16 on some projective trees; the paper does not give an example either way, so the cleanest check is to enumerate small trees and compute their proper rope covers.","The same rope-cover machinery works for general graphs, so the optimal hierarchical bracketing is a natural candidate for dependency-graph parsing, a direction the paper explicitly leaves open.","Because rope thickness bounds the needed index, the non-projective encoding has a built-in ceiling tied to a linguistic treebank property; if future treebanks exceed thickness 8, the label set grows but stays finite.","The observed accuracy pattern, better complete-tree match but worse labeled attachment score than redundant encodings, suggests compactness trades away redundancy; a direct test would be to add redundant semibrackets to the optimal encoding and measure whether labeled attachment score rises."],"forward_implications":["Any projective dependency tree can be tagger-encoded with 12 labels, shrinking the output vocabulary by 25% relative to the 4-bit encoding.","The proper rope cover minimizes brackets for every individual tree, so the optimal hierarchical bracketing is optimal tree-by-tree, not just on average.","Non-projective trees can be encoded directly without a pseudo-projective transformation, and the index bound 2 suffices for all tested treebanks except Ancient Greek, where index 3 covers the remaining trees.","The new encodings reach accuracy on par with 4-bit, 7-bit, and hexatagging baselines while being faster than all of them on English, because the label space is smaller and no intermediate constituent tree is required.","Pseudo-projectivity improves the projective optimal encoding on non-projective treebanks, sometimes beating the native non-projective encodings."],"supporting_citations":[{"why":"Supplies the rope cover definition, the uniqueness and greedy-cover algorithm, and the rope-thickness bound used for index sizes.","marker":"Yli-Jyrä (2019b)"},{"why":"Defines the 4-bit and 7-bit encodings that the paper proves to be instances of hierarchical bracketing and shows to be suboptimal.","marker":"Gómez-Rodríguez et al. (2023)"},{"why":"Introduces the basic bracketing encodings that hierarchical bracketing generalizes by reducing most arcs to single semibrackets.","marker":"Strzyz et al. (2019, 2020)"},{"why":"Provides the equivalent definition of projective trees used in the proofs of the label bounds.","marker":"Nivre (2006)"},{"why":"Presents hexatagging, the 8-label projective encoding used as a baseline and speed comparison.","marker":"Amini et al. (2023)"},{"why":"Defines the pseudo-projective transformation used in the experiments to boost projective encodings on non-projective treebanks.","marker":"Nivre and Nilsson (2005)"}],"fun_headline_variants":["Optimal bracket encoding cuts parsing labels from 16 to 12","Tighter dependency parsing encoding: 12 labels beat 16","New bracket scheme reduces dependency label set to 12","12 labels: optimal hierarchical bracketing for parsing"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The 12-label theorem relies on an unproved premise: in the proper rope cover of a projective tree, no node can head both a leftward structural arc and a rightward structural arc at the same time.","fun_headline_variants_meta":{"raw":{"variants":["Optimal bracket encoding cuts parsing labels from 16 to 12","Tighter dependency parsing encoding: 12 labels beat 16","New bracket scheme reduces dependency label set to 12","12 labels: optimal hierarchical bracketing for parsing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000996,"raw_usage":{"total_tokens":4157,"prompt_tokens":823,"completion_tokens":3334,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":439,"completion_tokens_details":{"reasoning_tokens":3267}},"tokens_in":439,"tokens_out":3334,"duration_ms":24426,"temperature":1.0,"reasoning_tokens":3267,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:51:03.013319+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find, or computationally search for, a projective dependency tree whose proper rope cover makes the same node the head of both a leftward and a rightward structural arc; such a tree would force one of the four excluded labels and falsify the 12-label theorem. A brute-force check of all small projective trees with the published greedy rope-cover algorithm settles the question.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the equivalent definition of projective trees used in the proofs of the label bounds."}],"review_version":1}