{"id":"dd2131e1-d8b6-46ae-9b6d-fa8205f33ce4","arxiv_id":"1908.11034","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"The authors formalize tensor-network contraction orders as contraction trees, link the space and time bottlenecks to carving-width and treewidth, and show experimentally that a Ratcatcher-based planner produces near-optimal orders on planar grid networks.","lead":"Tensor-network contraction time depends heavily on the order of pairwise contractions. This paper proposes carving-width, a planar-graph measure, as a fast heuristic for finding good contraction orders and reports benchmarks against an exact optimizer.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The empirical support for the central claim is conditional on Netcon finishing: Table 1 excludes the 16/30 L=10 and 1/30 L=9 timed-out instances from every rho, so the reported factor-of-3-to-4 ratios are not complete-case estimates.","rationale":"The theoretical core--the contraction-tree datatype, the equivalence to carving-decompositions, the Bs/Bt/Ct inequalities, and the polynomial-time Ratcatcher implementation--is a real contribution and I do not dispute it. The weak point is the inference from benchmark numbers to 'generally effective.' The reader's conditional verdict already identifies the exclusion of hard instances; my stress-test confirms that this is the load-bearing issue. A theorem cannot rescue the empirical claim because eq. (6) only gives Ct <= (|V|-2)(Bs)^1.5; with Bs approximately 2^34 in the table, that bound permits ratios many orders of magnitude above the observed 3-4, so the data are doing all the work. The authors' own outlier (rho approximately 249) and their explicit deferral of full PEPS tests (Section 4.2) reinforce the need to qualify the claim. No ad hominem is intended; this is a request for complete-case evidence and a more cautious wording. Since the reader's CONDITIONAL verdict already conditions acceptance on complete-case analysis, I do not change it.","tokens_in":49,"tokens_out":12077,"duration_ms":183596,"concrete_test":"Obtain the authors' sample generator and run Netcon to completion (or with a substantially longer time budget, e.g., 72 h per instance) on the 17 timed-out L=9/L=10 instances; recompute mean/median rho over all 30 samples per L. Report the complete-case values alongside the current asterisked values, and also report RatconCt/Bs_G as a worst-case lower-bound ratio for any instance where Netcon still cannot finish. If complete-case rho remains low, the selection-bias concern is answered; if it rises materially, the paper's claim should be restricted to 'effective on easy instances' until a better heuristic or a non-planar extension is demonstrated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract's 'generally effective heuristic' claim is an empirical statement. Its only quantitative support is Table 1, and Table 1 is not a complete-case table. Section 4.6 reports that Netcon was terminated after 7200 s for 1/30 L=9 samples and 16/30 L=10 samples, and that the asterisked cells 'had these incomplete samples excluded from their calculation.' All L=9 and L=10 rho entries (mean 12.28/3.36, median 3.11/2.74) are therefore computed over the sub-samples on which Netcon happened to finish. Since Netcon's runtime is itself a function of instance difficulty, the 17 missing instances are not missing at random; they are plausibly the hardest cases for exact optimization, and Section 4.6 already documents a separate L=9 outlier with rho approximately 249 that resisted thousands of edge contractions. If the missing cases have comparably poor ratios, the headline conclusion 'generally effective' does not follow from the data. This is compounded by the paper's own Section 4.2 statement that the intended PEPS bra-ket networks are non-planar and that tests 'on the full PEPS forms are deferred'; the experiments cover planar half-grids only, so the empirical claim is at best about planar grid-like networks, not the motivating workloads.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a contraction-tree abstraction for tensor-network contraction orders, in which arc labels encode space costs and node labels encode time costs, and proves bounds relating the space bottleneck Bs, the time bottleneck Bt, and the total contraction time Ct. It establishes equivalences between contraction trees and tree decompositions of line graphs (Theorems 1-2) and between contraction trees and carving decompositions (Theorem 3), and derives the bound Bs <= Bt <= Bs^1.5. The authors implement the Seymour-Thomas Ratcatcher algorithm ('Ratcon') to compute carving-width-optimal contraction trees for planar networks and benchmark them against Netcon on planar square half-grids with lognormal bond dimensions. The reported empirical claim is that Ratcon yields contraction orders whose total time is typically within a small factor of the exact optimum.","tokens_in":16494,"tokens_out":5880,"duration_ms":53061,"significance":"If the theoretical claims hold, the paper provides a useful datatype for tensor-network contraction, polynomial-time computation of space-optimal contraction orders for planar networks, and an open-source implementation at https://github.com/TensorCon. The equivalence results and the Bs-Bt-Ct bounds are clean contributions that connect carving-width and treewidth to a concrete contraction-cost model. The empirical evidence, however, currently supports only a restricted version of the abstract's claim, because the benchmark statistics are incomplete-case estimates and the experiments cover only planar half-grids rather than the motivating PEPS bra-ket networks.","major_comments":[{"comment":"The reported L=9 and L=10 statistics are not complete-case estimates. The text states that one of thirty L=9 samples and sixteen of thirty L=10 samples were terminated after 7200 seconds, and that asterisked cells exclude these incomplete samples. Because Netcon's runtime is longer for harder instances, the 17 excluded cases are not missing at random; they are likely the instances where exact optimization is most difficult, so the mean/median rho values (12.28/3.36 for L=9 and 3.11/2.74 for L=10) may substantially understate Ratcon's error factor on the full sample. The 'generally effective heuristic' claim in the abstract requires either a complete-case analysis, an imputation or documented bound for the excluded cases, or a qualified restatement of the claim.","section":"Section 4.6 and Table 1"},{"comment":"The motivating PEPS bra-ket networks are non-planar, and the paper states that tests on full PEPS forms are deferred. The experiments only cover planar half-grids without free edges. Thus the empirical part of the claim is limited to planar grid-like networks, and the abstract's 'generally effective heuristic' is not directly supported for the motivating workloads. Please either restrict the claim accordingly or provide a concrete argument why the planar half-grid results transfer to the non-planar full PEPS setting.","section":"Section 4.2"},{"comment":"The statement 'carw(G) = log Bs_G' is imprecise. Carving-width is defined for additive edge weights, whereas Bs is defined via products of bond dimensions; the equality can hold only after applying a logarithmic transformation to the edge weights, and 'up to logarithmic concavity' is not a defined concept. The one-sentence proof, which refers to transferring between the groups (N,+) and (R*,x), does not specify the exact mapping between carving decompositions and contraction trees for weighted graphs. Please restate Theorem 3 with explicit weights and a definition of the transformed carving-width, since Section 4.3 relies on this logarithmic mapping.","section":"Section 3.2, Theorem 3"},{"comment":"The proof of Eq. (7), on which the Bt <= Bs^1.5 bound depends, is too compressed and contains an apparent typo: 'delta_a' union delta_a'' = delta_a union delta_a'' = delta_a intersection delta_a' = delta_n' cannot hold as written, since the last equality uses an intersection sign where a union is intended. The inclusion-exclusion argument appears to be correct, but the derivation needs to be expanded and the set equalities corrected so that the lemma is verifiable.","section":"Section 3.3, Lemma 2"}],"minor_comments":[{"comment":"The remark that node labels could be identified with subsets of V but that this identification is not required is confusing, because the free contraction tree constructed later does identify nodes with subsets of V; please clarify what freedom the definition is intended to allow.","section":"Definition 4 and Remark"},{"comment":"The phrase 'modulo its 2-cuts delta_a' is unclear; I think the intended meaning is that the node labels alone define the tree-decomposition, while the arc labels are ignored or redundant.","section":"Theorem 1 proof"},{"comment":"The split rule writes edges(m') = {a',a'',a'''} but edges(m'') = {a'''} union (edges(n) \\ {a,a'}); the removed arcs are inconsistent between the two nodes, which makes the splitting step difficult to follow.","section":"Theorem 2, step 3"},{"comment":"Square grids are planar and have genus 0; the phrase 'high genera' is inaccurate and should be reworded.","section":"Section 4.2"},{"comment":"The variables C_s and c_s are not defined inside the algorithm; please clarify that c_s(node) is the single-arc space cost and C_s is the accumulated space bottleneck.","section":"Algorithm 1"},{"comment":"The sentence 'Ratcon underperforms for small L, where the time lost in repeated ECs dominates, then becomes exponentially faster at L=9 or 10' is at odds with Table 1, where tau for L=5 is 47.87 (mean) and 35.11 (median); the intended comparison should be stated more carefully.","section":"Section 4.6"}],"recommendation":"major_revision","confidential_remarks":"The paper is honest about the timeouts and the planarity limitation, but the abstract's 'generally effective' claim goes beyond what Table 1 can support in its current form. The theoretical core is sound and worth publishing after the empirical claims are qualified or strengthened, and after Theorem 3 and Lemma 2 are stated more precisely."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth a look for two reasons. First, it gives a clean, systematic development of the contraction-tree datatype and shows how the space and time bottlenecks map onto carving-width and weighted treewidth of the line graph. The bounds Bs ≤ Bt ≤ Bs^1.5 are simple but useful, and the proof that a tree-decomposition can be transformed into a contraction tree is reasonable. Second, they actually implemented the Seymour–Thomas Ratcatcher and evaluated it against Netcon, an external exact optimizer. That is real work, and the code is on GitHub. For planar grid-like networks, the heuristic does appear to produce contraction orders within a small factor of optimal on the instances that were compared, in a fraction of the time.\n\nThe soft spots are mostly about the empirical claim. The abstract says carving-width makes a 'generally effective heuristic' for limiting total contraction time, but the supporting table excludes 16 of 30 L=10 samples and 1 of 30 L=9 samples because Netcon timed out. Those timeouts are not random: Netcon's runtime tracks instance difficulty, so the missing cases are likely the hard ones. Section 4.6 even reports a separate L=9 outlier with ρ ≈ 249. The reported means and medians are therefore conditional on Netcon finishing, and the headline conclusion does not follow from the data. The authors should have provided a complete-case analysis, or at least clearly labeled the ratios as conditional. Also, the experiments are on planar half-grids only; full PEPS bra-ket networks are non-planar, and the paper defers those tests. That is fine as a limitation, but it should temper the 'generally effective' phrasing.\n\nThere are minor mathematical rough edges: the proof of Lemma 2 is compressed, and Theorem 3's 'up to logarithmic concavity' is imprecise. These are not fatal; a referee should ask the authors to tighten them, not to redo the paper. The novelty is moderate—the connection between carving-width and contraction order was already noted by Aharonov–Landau–Makowsky and de Oliveira Oliveira—but the contraction-tree framing and the first benchmark of a Ratcatcher-based tensor-network heuristic are worth publishing after revision.\n\nFor a practitioner working with planar networks, this is a useful benchmarking tool against approximate contraction methods. I would send it to peer review: the theory is sound enough, the code is real, and the empirical weakness is fixable with a revised analysis and a more careful abstract.","headline":"A genuinely useful contraction-tree framing and a working Ratcatcher implementation, but the headline 'generally effective heuristic' claim is undercut by timeouts excluded from the reported ratios.","tokens_in":17000,"tokens_out":1361,"would_cite":true,"duration_ms":15464,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","05C10","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper argues that carving-width, computed by the Ratcatcher algorithm for planar graphs, is a practical heuristic for near-optimal tensor-network contraction orders.","keywords":["tensor networks","contraction ordering","carving-width","contraction trees","Ratcatcher","planar graphs","PEPS","exact tensor contraction"],"falsifier":"Let Netcon run to completion, or with a much larger budget, on the sixteen $L=10$ half-grids that were stopped at 7200 seconds, and compute Ratcon's total-time ratio $\\rho$ on those graphs alone; if their mean $\\rho$ is far above the 3.36 reported for the fourteen finished instances, the claim that carving-width is generally effective at limiting total contraction time would be refuted. A complementary check: find a planar weighted grid on which every minimum-carving decomposition forces one internal node whose weight far exceeds the optimal total time.","tokens_in":15968,"feed_emoji":"🧮","tokens_out":15073,"duration_ms":150600,"temperature":0.7,"pith_summary":"This paper tries to establish that carving-width, a graph measure of the largest cut a binary routing tree must make, is a practical guide to the cost of contracting a tensor network. It introduces the contraction tree as a shared data type: arc labels record the size of intermediate tensors (space) and node labels record the arithmetic cost of each pairwise contraction (time), so the same tree encodes both bottlenecks. The authors implement the Ratcatcher algorithm to compute carving-width in polynomial time for planar networks and use it to build contraction orders, a pipeline they call Ratcon. On planar square half-grids meant to resemble PEPS states, Ratcon finds orders whose total contraction cost is typically within a factor of about three to four of the exact optimum, while the search itself becomes much faster than exact search as the grids grow.","feed_headline":"Carving width fast-tracks near-optimal tensor contractions","feed_subtitle":"Ratcon finds orders within a few times the exact cost on planar grids; its speed advantage grows with grid size.","key_machinery":"The load-bearing object is the free contraction tree, a full binary tree whose leaves are the tensors of the network. Removing an arc splits the leaves into two sets and labels the arc with the product of the weights of the edges crossing that split, giving the space bottleneck $B_s^T$; each internal node has three incident subtrees and its label is the product over the 3-cut, giving time cost $w_n = \\sqrt{w_a w_{a'} w_{a''}}$ in terms of its three adjacent arc labels. This identity plus the bounds $B_s\\le B_t\\le (B_s)^{1.5}$ ties the spatial measure to total time, and the isomorphism between contraction trees and carving-decompositions lets the polynomial-time Ratcatcher decision procedure for planar graphs compute the optimal space bottleneck. The remaining machinery turns the width into an order: an edge-contraction construction of the decomposition, repeated random trials to choose among equally space-optimal trees, rooting at the cheapest edge, and a linear-time recursive sequencing algorithm that conserves memory.","core_discovery":"The central claim is that minimizing the space bottleneck, not the total time directly, is a viable route to near-optimal contraction orders on planar tensor networks. Formally, a free contraction tree is a carving-decomposition: the label of an arc is the product of bond dimensions crossing a 2-cut, and the label of an internal node is the product crossing the corresponding 3-cut. With edge weights mapped to logarithms, the carving-width of the graph equals $\\log_2 B_s^G$, the logarithm of the smallest achievable space bottleneck. Ratcon computes that width with the Ratcatcher, assembles a carving-decomposition through random edge contractions, roots the tree at a minimum-weight edge, and emits a concrete contraction sequence. Benchmarks on $L\\times L$ half-grids, $L=5,\\dots,10$, with lognormal bond dimensions show that Ratcon's sequences have total time within a small constant factor of the exact Netcon optimum on the instances Netcon can finish (mean $\\rho\\approx 3.36$ at $L=10$), while Ratcon's running-time advantage grows with $L$; one $L=9$ outlier has error factor 249, and the sixteen hardest $L=10$ instances are excluded from the reported ratios.","pith_inferences":["An extension the paper does not run: applying Ratcon to other planar network families, such as hexagonal PEPS half-lattices or random planar graphs with lognormal weights, would test whether the factor-3-to-4 ratio is a property of planar carving-width generally or of square-grid geometry.","The single error factor of 249 hints that pure space-bottleneck minimization can occasionally miss a time-dominant contraction; a local post-pass that swaps sibling subtrees or evaluates total time among a handful of equally $B_s$-optimal trees might remove such outliers while staying polynomial, but this is not tested in the paper.","Full PEPS bra-ket networks are non-planar, so the paper's stated motivation of hundreds-of-tensors exact contractions is not yet delivered; a planarization that avoids squaring bond dimensions would be the natural next step, and the paper explicitly defers it.","Since the Ratcatcher phase runs in time proportional to $\\log_2 B_s^G$ rather than to $B_s^G$, the width-finding part stays cheap even for memory-heavy networks; in practice the edge-contraction sampling factor $N$, not the width computation, is likely to dominate preprocessing cost."],"forward_implications":["On planar grid-like networks, near-optimal contraction orders can be found in polynomial time, roughly $O(N|V|^4\\log B_s^G)$ with $N$ random trials, rather than by the exponential branch-and-bound search used by exact optimizers.","The search-time advantage grows with grid size: Ratcon is slower than Netcon for small $L$ but about ten times faster on the completed $L=10$ subset, so the heuristic pays off exactly in the regime where exact search begins to time out.","Space-optimality does not imply time-optimality, as the paper's $K_4$ example shows, so the practical recipe is to hedge by running a Netcon-style exact search in parallel with the Ratcon order.","For the tested $L=10$ instances, the break-even point is about 500 GFLOPS: on faster machines the extra arithmetic of a Ratcon order is outweighed by the reduced search time.","Because any tree-decomposition of the line graph (the graph whose vertices are the original edges) can be converted into a contraction tree without increasing width, advances in weighted treewidth computation translate directly into better contraction orders."],"supporting_citations":[{"why":"Defines carving-width and the Ratcatcher decision procedure that Ratcon uses to compute the optimal space bottleneck for planar graphs.","marker":"[25]"},{"why":"Supplies Netcon, the exact contraction-order optimizer whose optimal total-time baseline Ratcon is compared against in the benchmarks.","marker":"[21]"},{"why":"Provides the edge-contraction method that turns a computed carving-width into an actual carving-decomposition, the construction step at the heart of Ratcon.","marker":"[11]"},{"why":"Supplies practical optimizations for the Ratcatcher implementation that the authors adopt and partially incorporate.","marker":"[5]"},{"why":"Establishes the tensor-network contraction complexity model that the paper's space and time bottleneck definitions generalize.","marker":"[16]"}],"fun_headline_variants":["Space bottleneck predicts fast tensor contraction orders","Carving-width guides near-optimal contraction sequences","Ratcatcher finds contraction orders via space constraint","Planar tensor nets: minimize space, save time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The experimental case assumes that the $L=10$ graphs on which the exact optimizer Netcon finished within two hours represent the full distribution; if the sixteen unfinished graphs are exactly the cases where space-optimal orders are time-wasteful, the reported error ratios overstate how generally effective carving-width is.","fun_headline_variants_meta":{"raw":{"variants":["Space bottleneck predicts fast tensor contraction orders","Carving-width guides near-optimal contraction sequences","Ratcatcher finds contraction orders via space constraint","Planar tensor nets: minimize space, save time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000224,"raw_usage":{"total_tokens":1422,"prompt_tokens":869,"completion_tokens":553,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":485,"completion_tokens_details":{"reasoning_tokens":495}},"tokens_in":485,"tokens_out":553,"duration_ms":6659,"temperature":1.0,"reasoning_tokens":495,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:26:35.910145+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Let Netcon run to completion, or with a much larger budget, on the sixteen $L=10$ half-grids that were stopped at 7200 seconds, and compute Ratcon's total-time ratio $\\rho$ on those graphs alone; if their mean $\\rho$ is far above the 3.36 reported for the fourteen finished instances, the claim that carving-width is generally effective at limiting total contraction time would be refuted. A complementary check: find a planar weighted grid on which every minimum-carving decomposition forces one internal node whose weight far exceeds the optimal total time.","supporting_citations":[{"cited_title":"Faster identification of optimal con- traction sequences for tensor networks","cited_arxiv_id":null,"evidence_quote":"Supplies Netcon, the exact contraction-order optimizer whose optimal total-time baseline Ratcon is compared against in the benchmarks."},{"cited_title":"Planar branch decompositions I: The ratcatcher","cited_arxiv_id":null,"evidence_quote":"Provides the edge-contraction method that turns a computed carving-width into an actual carving-decomposition, the construction step at the heart of Ratcon."},{"cited_title":"Practical algorithms for branch-decompositions of planar graphs","cited_arxiv_id":null,"evidence_quote":"Supplies practical optimizations for the Ratcatcher implementation that the authors adopt and partially incorporate."}],"review_version":1}