{"id":"303b8787-8eb5-4616-96bb-d186377b2b5f","arxiv_id":"2606.18520","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Proves constant-dimension 3 reachability embeddings for directed trees, O(t log n) for treewidth-t graphs, with lower bounds of Omega(n) for general DAGs and Omega(t/log(n/t)) for treewidth t, plus real-dataset results.","lead":"This paper proves reachability embeddings exist in dimension 3 for any directed tree and in O(t log n) dimensions for graphs of treewidth t, with matching lower bounds. A smart generalist might read it because compact embeddings could make hierarchical search and retrieval systems more efficient at scale.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader flagged the embedding definition itself as the weakest assumption, but that is simply the problem statement for an existence proof; the paper supplies both upper-bound constructions and lower bounds that align with it. With no concrete gap in the argument visible, the UNVERDICTED status remains appropriate pending full proof inspection, but no adjustment to the verdict category is warranted.","tokens_in":1761,"tokens_out":273,"duration_ms":40579,"concrete_test":"Take the explicit construction for trees given in the paper and instantiate it on a path of length 100 and on a complete binary tree of depth 10; verify that the resulting 3-dimensional points satisfy the reachability predicate exactly (ancestor-descendant pairs only) with no false positives.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is an existence result: constant-dimension (d=3) reachability embeddings exist for arbitrary directed trees, with an O(t log n) construction for treewidth-t graphs. The abstract states matching/near-matching lower bounds and notes that the only requirement is faithful capture of ancestor-descendant reachability. No internal inconsistency, hidden dependence on depth or n in the tree case, or unsecured assumption about the geometric predicate is apparent from the stated claims.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims that any directed tree admits a reachability embedding in constant dimension 3 independent of size or depth; that graphs of treewidth t admit embeddings of dimension O(t log n); that these are complemented by lower bounds of Omega(n) for general DAGs and Omega(t / log(n/t)) for treewidth-t graphs; that additional upper/lower bounds exist parameterized by the number of cross-edges; and that the embeddings can be constructed on real-world datasets and yield smaller dimensions than prior work in high-recall regimes.","tokens_in":1855,"tokens_out":350,"duration_ms":25395,"significance":"If the existence proofs and constructions hold, the results would be significant for geometric representations in hierarchical retrieval. The constant-dimension result for arbitrary trees (independent of depth or n) and the treewidth parameterization provide dimension bounds that depend only on structural parameters rather than instance size, improving on prior work whose bounds degrade with depth. The matching or near-matching lower bounds and the empirical demonstration on real data are additional strengths; the parameter-free character of the tree result is noteworthy.","major_comments":[],"minor_comments":[{"comment":"Abstract: the citation 'You et al. [NeurIPS '25]' should include a full bibliographic entry or arXiv identifier for completeness.","section":"Abstract"},{"comment":"The manuscript should clarify in the main text (e.g., near the treewidth construction) whether the O(t log n) bound is achieved by an explicit polynomial-time algorithm or only by an existence argument.","section":"Section on treewidth embeddings"}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive assessment, the recognition of the constant-dimension result for trees, the treewidth parameterization, the lower bounds, and the empirical results. The recommendation for minor revision is appreciated. No specific major comments were raised in the report.","responses":[],"tokens_in":1329,"tokens_out":61,"duration_ms":11608,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The standout result is that any directed tree admits a reachability embedding in dimension 3, independent of size or depth. That is new relative to the You et al. bounds that scaled with depth or number of descendants. The O(t log n) construction for treewidth-t graphs is a natural extension and comes with near-matching lower bounds of Omega(t / log(n/t)). They also handle the cross-edge parameterization and show the embeddings can be built on real data with smaller dimensions than prior guaranteed methods in high-recall regimes.\n\nThe paper is clear on what it proves and what the geometric predicate actually requires: just ancestor-descendant ordering. No hidden dependence on n or depth appears in the tree case, and the lower bounds for general DAGs (Omega(n)) line up with intuition.\n\nThe empirical part is the softer spot. The abstract claims practical gains, but without seeing the exact baselines, dataset sizes, or how the embeddings are optimized in practice, it is difficult to judge how much the theory translates to retrieval speed or accuracy. That section feels more like a sanity check than a full evaluation.\n\nThis is for researchers working on geometric methods for hierarchical retrieval or knowledge graphs. Anyone thinking about parameterized embeddings or constant-dimension representations will find the tree and treewidth results worth reading. The claims are specific enough and the lower bounds tight enough that it should go to referees rather than a desk reject.","headline":"Constant dimension 3 for any directed tree is the real advance, with the treewidth parameterization as a useful follow-on.","tokens_in":2332,"tokens_out":353,"would_cite":true,"duration_ms":14225,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Reachability in directed trees can be represented by embeddings in just three dimensions.","keywords":["reachability embeddings","directed trees","treewidth","hierarchies","DAGs","geometric representations","embedding dimension"],"falsifier":"Exhibit one directed tree together with an explicit enumeration of its reachability pairs such that no assignment of 3-dimensional coordinates makes the geometric condition hold exactly for those pairs and fail for the others.","tokens_in":2688,"feed_emoji":"📐","tokens_out":703,"duration_ms":25612,"temperature":0.7,"pith_summary":"The paper establishes that any directed tree admits a geometric embedding of constant dimension 3 in which ancestor-descendant reachability is preserved exactly. This bound is independent of tree size or depth and improves on earlier constructions whose dimension grew with the number of nodes in deep hierarchies. The result extends to graphs of treewidth t with embeddings of dimension O(t log n), accompanied by nearly matching lower bounds. The constructions are shown to produce smaller dimensions than prior guaranteed methods when applied to real datasets at high recall. These guarantees matter because they allow hierarchical retrieval systems to use fixed low-dimensional vectors while retaining exact theoretical correctness for tree-structured data.","feed_headline":"Trees admit 3D reachability embeddings regardless of size","feed_subtitle":"Constant dimension 3 works for any directed tree; dimension scales as O(t log n) once treewidth t is fixed.","key_machinery":"Reachability embedding: a mapping from nodes of a DAG to points in Euclidean space such that one node reaches another precisely when the corresponding points satisfy the geometric condition that encodes the ancestor-descendant partial order.","core_discovery":"For any directed tree there exists a reachability embedding in dimension 3. For graphs of treewidth t the paper constructs embeddings of dimension O(t log n). Matching or near-matching lower bounds are given: dimension Omega(n) is necessary for arbitrary DAGs and Omega(t / log(n/t)) for treewidth-t graphs. Additional bounds are obtained in terms of the number of cross-edges. The embeddings are realized on real-world data and yield smaller dimensions than previous theoretical embeddings in high-recall regimes.","pith_inferences":["The constant-dimension result for trees suggests that practical hierarchy-aware models could keep embedding size fixed while scaling to arbitrarily large trees.","The treewidth parameterization may extend to other sparse graph families that admit low-treewidth decompositions, such as series-parallel graphs.","Efficient construction algorithms for the embeddings would turn the existence proofs into practical preprocessing routines for retrieval systems."],"forward_implications":["Hierarchical retrieval on tree data can use fixed three-dimensional vectors instead of vectors whose length scales with depth or node count.","Graphs of bounded treewidth admit embeddings whose dimension grows only logarithmically with n once the treewidth parameter is fixed.","Lower bounds show that dimension linear in n is unavoidable for arbitrary DAGs, so the tree and treewidth restrictions are essential.","Embeddings parameterized by cross-edge count give further dimension reductions when the DAG is close to a tree."],"fun_headline_variants":["Directed trees embed reachability in fixed dimension 3","Any directed tree has 3D reachability embedding","Treewidth t yields O(t log n) reachability embeddings","Lower bounds require Omega(n) dims for general DAGs","Compact reachability embeddings scale with treewidth t"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The ancestor-descendant ordering of the input DAG can be captured exactly by some geometric relation on points in low-dimensional space without requiring extra metric or inner-product constraints.","fun_headline_variants_meta":{"raw":{"variants":["Directed trees embed reachability in fixed dimension 3","Any directed tree has 3D reachability embedding","Treewidth t yields O(t log n) reachability embeddings","Lower bounds require Omega(n) dims for general DAGs","Compact reachability embeddings scale with treewidth t"]},"model":"grok-4.3","cost_usd":0.002684,"raw_usage":{"total_tokens":1555,"prompt_tokens":748,"num_sources_used":0,"completion_tokens":76,"cost_in_usd_ticks":26837000,"prompt_tokens_details":{"text_tokens":748,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":731,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":748,"tokens_out":76,"duration_ms":6545,"temperature":1.0,"reasoning_tokens":731,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-26T22:10:23.161398+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Exhibit one directed tree together with an explicit enumeration of its reachability pairs such that no assignment of 3-dimensional coordinates makes the geometric condition hold exactly for those pairs and fail for the others.","supporting_citations":[],"review_version":1}