{"id":"3e638591-71f6-4057-a9d7-fad289b5cca2","arxiv_id":"2607.18606","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under positive-reach initial sets, Lipschitz dynamics, and lower-bounded sampling densities, Hausdorff-accurate sampling-based reachability needs Õ((e^{3LT}/r)^n) samples and cannot require fewer than Ω((e^{LT}/r)^n).","lead":"This paper proves that turning a cloud of simulated trajectories into a Hausdorff-accurate picture of a reachable set takes exponentially many samples in both state dimension and time horizon, and that no clever method can beat this in the worst case. It also pins down the geometric and dynamical conditions under which a probabilistic coverage guarantee can be promoted to a geometric one.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the flagged backward-well-posedness gap is not load-bearing; forward well-posedness plus Lipschitz uniqueness already supply the injectivity needed.","rationale":"The stress-test pass focused on the load-bearing status of the reader's flagged assumption. The reader identified backward-time well-posedness as the weakest assumption, arguing that the injectivity proof in Proposition 4 may fail if trajectories can merge or leave X backward in time. On close reading, this is not a genuine gap. The standing convention in Section 2 states that φ(t,·) is well defined and unique on the relevant initial states for all t ∈ [0,T]. For any endpoint y ∈ S_T with y = φ(T,x), the reverse-time curve η(s) := φ(T-s,x) is well defined for all s ∈ [0,T] precisely because it is the forward trajectory from x evaluated at times no larger than T. Thus backward existence is automatic. Lipschitzness of -F then gives uniqueness of the reverse IVP, which directly implies injectivity of φ(T,·). The lower Lipschitz bound and the volume-distortion bound (Proposition 4 parts 3 and 4) use the same device, and they are valid. I also checked the lower-bound construction: the hole-in-ball instances satisfy the metric and density conditions, the reach calculation via Lemma 4 is correct, and the overlap computation uses constant product densities on equal-volume supports, so the N-fold overlap is exactly (1 - (h/R)^n)^N. No hidden assumption breaks the minimax argument. The central claim therefore stands. The paper's conditional verdict is still reasonable on other grounds—the abstract states a tight sandwich without noting the e^{3LT} vs e^{LT} factor and the lower-bound regime restrictions, and the experimental slope fits in Table 2 lack uncertainty quantification. These are minor and addressable, and they do not alter the correctness of the main mathematical result.","tokens_in":26497,"tokens_out":35827,"duration_ms":383419,"concrete_test":"Re-derive Proposition 4 from the stated assumptions alone: for any a,b ∈ S0 with φ(T,a)=φ(T,b), define η_a(s) := φ(T-s,a) and η_b(s) := φ(T-s,b) on [0,T]; show both solve η' = -F(η) with the same initial value, then apply the standard uniqueness theorem for Lipschitz ODEs to conclude a = b. If this 10-line derivation goes through, the reader's weakest-assumption concern is resolved and no backward-well-posedness condition beyond the paper's forward convention is needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the paper as establishing its central claim: the sample complexity of Hausdorff-accurate reachable-set recovery is exponential in state dimension n and time horizon T, with upper and lower bounds that match up to constants and logarithmic factors. The reader's weakest assumption faults Proposition 4's injectivity/volume-distortion argument for implicitly assuming backward existence on S_T. This concern does not land. In Proposition 4, the 'reverse-time' trajectory η_a(s) := φ(T-s, a) is simply the forward trajectory from a ∈ S0 evaluated at time T-s ∈ [0,T]; its existence and uniqueness are guaranteed by the paper's standing forward well-posedness convention. If φ(T,a)=φ(T,b) for some a,b ∈ S0, then η_a and η_b are two solutions of η' = -F(η), with -F L-Lipschitz, sharing the same initial value at s=0. Standard ODE uniqueness gives η_a = η_b, hence a=b. The lower Lipschitz and volume-distortion bounds follow from the same argument, so no extra backward-existence axiom is introduced. I found no other load-bearing flaw: the lower-bound construction satisfies the family conditions (uniform density, positive reach of the complement, L-Lipschitz F), and the product-measure overlap calculation is correct because the two candidate densities are constant on their supports. The remaining issues—the abstract's omission of the e^{3LT} versus e^{LT} gap and the lightly fitted experimental slopes—are presentation/empirical matters, not threats to the core theorems.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the finite-sample Hausdorff recovery of reachable sets S_T = φ(T, S_0) from N i.i.d. endpoint samples. It defines a problem family F_{R,L,r0,ρ} requiring bounded initial sets of volume ω_n R^n, positive reach of the complement of S_0, L-Lipschitz autonomous dynamics, and a uniform lower bound ρ on the initial sampling density. The main results are: (i) local Lebesgue-mass and endpoint-probability lower bounds (Propositions 1–3, Corollaries 1–2); (ii) an upper bound (Theorem 1) showing that N ≥ 2^{2n} e^{3nLT} R^n/(ρ r^n) [log(2^{3n} e^{nLT} R^n/r^n) + log(1/δ)] samples suffice for r-inner coverage by any estimator containing its samples, with Corollary 3 giving a Hausdorff guarantee under an additional outer-deviation condition; and (iii) a minimax lower bound (Theorem 2) showing that any estimator requires N ≥ e^{nLT} R^n/(2^{n+1} r^n) log(1/(2δ)) samples on some admissible instance. The lower bound uses two punctured-ball initial sets with F(x)=Lx and an overlap/ testing argument. Experiments on a non-Lipschitz 2D example and MuJoCo robot arms illustrate the predicted dimension/horizon scaling.","tokens_in":26823,"tokens_out":20598,"duration_ms":226923,"significance":"If the results are correct, the paper makes a substantial contribution. It converts a previously informal intuition — that probability-mass guarantees do not imply geometric accuracy — into a precise sufficient condition (positive reach plus Lipschitz dynamics plus density lower bound) under which Hausdorff recovery is possible, and it proves that exponential dependence on state dimension and time horizon is not an artifact of a particular algorithm. The lower-bound construction is elegant and satisfies all conditions of the problem family. I specifically checked the flagged concern about Proposition 4: the reverse-time trajectory η_a(s) := φ(T−s, a) is simply the forward trajectory from a evaluated at time T−s, so its existence and uniqueness are already guaranteed by the standing forward well-posedness convention and by L-Lipschitzness of F. No additional backward well-posedness axiom is introduced. The paper provides detailed appendix proofs and reproducible code. The main caveat is that the upper and lower rates differ by a factor e^{2nLT}, so the exact minimax rate is not settled; nevertheless the central qualitative claim is well supported.","major_comments":[],"minor_comments":[{"comment":"The condition supp(P0)=S0 is not consistent with the usual measure-theoretic definition of support for an open set, since a measure whose density is positive exactly on an open set has support equal to its closure. Please either define an 'essential support' or write supp(P0)=bar{S0} and adjust Lemma 1 and the statements of S_T accordingly.","section":"Section 2, Definition 2"},{"comment":"Proposition 1 is stated for x in S0, but Lemma 2 applies it to centers z_j in a maximal β-separated subset of bar{S0}, which may lie on the boundary. The mass bound does extend to the closure, either by a density/continuity argument or by a rolling-ball argument with the center at distance r0 along the inward normal; please state this explicitly so that the covering-number proof is airtight as written.","section":"Appendix B.1 / B.4, Prop. 1 and Lemma 2"},{"comment":"The upper and lower bounds differ by e^{2nLT}, not merely by constants and logarithmic factors. The phrase 'matching upper- and lower-bound perspectives' in the conclusion should be softened; the paper establishes a sandwich, not an exact minimax rate.","section":"Abstract and Section 6"},{"comment":"There are several presentation issues: 'an minimax' in the abstract and Section 1; 'And Let R denotes' in Section 1; the proof of Theorem 2 refers to a condition '(B.4)' that is not labeled; Table 2 headings 'Dimension 4/6/8' should be explicitly tied to the state dimension 2n of the n-link arm to avoid confusion.","section":"Throughout"},{"comment":"The fitted relation N ≳ (A_n/r)^{a n^b + c} is based on slopes at only three dimensions (n=2,3,4 links, i.e., state dimensions 4,6,8) and a chosen functional form. It should be described as an empirical trend rather than a tested scaling law, especially because the theoretical bounds leave room for dimension-dependent constants.","section":"Appendix C.3"}],"recommendation":"minor_revision","confidential_remarks":"I found no load-bearing correctness errors. The paper is a good fit for the venue and the claims are supported by the proofs. The main weaknesses are notational sloppiness around closures/support and overstatement of the degree to which the upper and lower bounds match. The boundary issue in Lemma 2 is a local fix and does not change the conclusions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a serious look. The paper gives the first clean minimax statement I know for Hausdorff-accurate reachable-set recovery from endpoint samples: an upper bound of \\tilde{O}((e^{3LT}R/r)^n) and a lower bound of \\Omega((e^{LT}/r)^n) that holds for every estimator, under positive reach of the complement, L-Lipschitz dynamics, and a uniform density lower bound. The exponential dependence on dimension and horizon is real, not an artifact of a particular method.\n\nThe formulation as geometric support estimation under flow distortion is genuinely new in this literature, and the local mass propagation arguments are sound. The reader's weakest-assumption worry about backward-time well-posedness in Proposition 4 does not land. The reverse-time trajectories are just forward trajectories evaluated at T-s, and uniqueness of the forward flow already gives injectivity. No extra backward existence axiom is introduced. I checked the hard-instance construction too: the punctured balls satisfy the reach and density conditions, and the product-measure overlap calculation is correct.\n\nSoft spots, in proportion: the abstract slightly overstates the result. The upper and lower bounds differ by e^{2nLT}, so the exact minimax rate is not settled; the lower bound also has regime restrictions (R >= 4r0, small r). That's acceptable for a first result, but the abstract's language suggests a tighter match than the theorems deliver. The experiments are thin: only three state dimensions (4, 6, 8) for the slope fits, no uncertainties on the slopes, and the fitted exponent model in Table 3 has three parameters for three data points. It's illustrative, not confirmatory. Also, the code link points to an unrelated repository (JeanLew01), which needs fixing before anyone can reproduce anything.\n\nThe citation pattern is appropriate; the relationship to Lew et al. is clearly stated, and the limitations section honestly restricts the results to autonomous dynamics.\n\nWho is this for? People working on data-driven reachability, support estimation, and safe control will get a clear picture of what sampling-based methods can and cannot promise in Hausdorff distance. It deserves a serious referee, and I would engage with it. With the abstract toned down and the experiments given proper uncertainty quantification, it would be a solid publication.","headline":"A solid minimax sample-complexity result for Hausdorff-accurate sampling-based reachability; the backward-well-posedness worry is a red herring, but the abstract and the experiments overstate a bit.","tokens_in":27345,"tokens_out":1853,"would_cite":true,"duration_ms":30373,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["93B03","62G05","62C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Sampling a reachable set to guaranteed Hausdorff accuracy has sample cost exponential in state dimension and time horizon, and no estimator avoids it.","keywords":["reachability analysis","sample complexity","Hausdorff distance","support estimation","positive reach","Lipschitz dynamics","minimax lower bound","autonomous dynamical systems"],"falsifier":"A counterexample would be an admissible instance in the problem family where some r-ball around a reachable point carries less than the promised probability mass Γ_T(r), despite positive reach, Lipschitz dynamics, and uniform density. One can test this by numerically integrating the flow on a contracting system and checking whether inf_y P_T(B_r(y)∩S_T) stays above ρ 2^{-n} e^{-3nLT} (r/R)^n for all r ≤ e^{LT} r0; if it fails, the upper bound overstates the true sample requirement.","tokens_in":26369,"feed_emoji":"🎯","tokens_out":5746,"duration_ms":65283,"temperature":0.7,"pith_summary":"The paper asks how many endpoint samples are needed to approximate the reachable set of an autonomous dynamical system in Hausdorff distance, not just in probability mass. It defines a problem family where the initial set has positive reach, the dynamics are Lipschitz, and sampling density is bounded below, and proves that under these conditions a probability-mass guarantee upgrades to an r-accurate Hausdorff guarantee. The sample complexity is exponential in state dimension and time horizon: roughly (e^{LT}/r)^n trajectories are necessary on some instance, and slightly more, (e^{3LT}/r)^n up to log factors, are sufficient. The lower bound is worst-case over the family, so the exponential scaling is intrinsic to the problem class, not an artifact of any particular estimator. The paper also shows experimentally that adversarial sampling improves constants but cannot change this scaling.","feed_headline":"Reachable-set sampling cost is unavoidably exponential","feed_subtitle":"Even the best estimator needs roughly (e^{LT}/r)^n trajectories for Hausdorff accuracy; smarter sampling only sharpens constants.","key_machinery":"The load-bearing object is the local endpoint probability lower bound Γ_T(r) = ρ 2^{-n} e^{-3nLT} (r/R)^n, which says every r-ball centered at a reachable point carries at least this much probability mass. It is assembled from three ingredients: positive reach of the initial set's complement gives local volume thickness; L-Lipschitz flow gives bi-Lipschitz distortion and volume preservation up to e^{-nLT}; and the density lower bound converts volume into probability. The upper bound follows by covering the reachable set with r/2-balls and applying a union bound. The lower bound uses two nearly identical admissible instances whose endpoint supports are separated by more than 2r, so any accura","core_discovery":"The central claim is a characterization, matching up to constants in the exponent, of sampling-based reachable-set recovery. For any estimator whose output contains all sampled endpoints, N ≥ c (e^{3LT} R/r)^n (log(...)+log(1/δ)) samples suffice for every point of the true reachable set to lie within r of the estimate, provided the initial complement has positive reach r0, the vector field is L-Lipschitz, and the sampling density is bounded below by ρ/|S0|. Conversely, a minimax lower bound shows that if N < (e^{LT} R/r)^n / (2^{n+1}) log(1/(2δ)), there exists an admissible instance for which every estimator fails with probability > δ. The flow factor e^{nLT} appears because the dynamics dis","pith_inferences":["A natural extension of the worst-case bound is an instance-dependent version: the effective exponent should be e^{Λ_T}, where Λ_T is the maximum log volume expansion of the flow over the initial set, so systems whose dynamics contract or preserve volume may require far fewer samples than the worst-case e^{nLT}.","For robotic systems with low-dimensional structure, such as manipulators moving near a manifold, the relevant dimension in the r^{-n} factor may be the intrinsic dimension of the uncertainty set rather than the ambient state dimension; this could be tested by measuring sample complexity along the manifold.","A concrete testable extension: compute the infimum endpoint local mass γ_T(r) on a given system and check whether the sample requirement tracks 1/γ_T(r) rather than the global worst-case bound; the paper hints at this but does not develop it.","The minimax construction uses uniform distributions on two sets differing by a small hole; for non-uniform or strongly adaptive sampling laws the overlap argument would need reworking, so it remains open whether any adaptive law can do more than improve constants."],"forward_implications":["If the paper is right, any method that promises Hausdorff-accurate reachable-set certificates must spend at least Ω((e^{LT}/r)^n) trajectories on some admissible problem, so high-dimensional safety verification cannot rely on sampling alone.","Probability-mass coverage guarantees, the common form of finite-sample reachability results, can be upgraded to geometric accuracy only when local thickness, Lipschitz regularity, and a uniform density lower bound are present; without them a thin low-probability region can be missed while the mass error stays small.","The upper bound gives a concrete estimator-agnostic sample budget for inner coverage: for accuracy r, it is sufficient that every r/2-ball centered on the reachable set receives a sample, and the required N is dominated by (e^{3LT} R/(ρ^{1/n} r))^n.","Smarter sampling schemes such as adversarial sampling can lower constants and improve finite-sample error, but cannot alter the dimension-dependent exponent.","The paper explicitly limits its results to autonomous or closed-loop dynamics; open-loop reachable sets, where reachability is a union over a control set, are outside the scope of the volume-distortion and density-propagation arguments."],"fun_headline_variants":["Reachability sampling: exponential cost is unavoidable","Sampling reachable sets: curse of dimensionality, proven","Exponential sample complexity for reachable sets, no escape","Matching bounds: reachability sampling is inherently exponential","You can't beat exponential sampling for reachable sets"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The argument needs the time-T flow map to be injective with an e^{LT}-Lipschitz inverse on the reachable set; if backward trajectories from some endpoint fail to exist or uniqueness fails over the horizon, the volume lower bound that anchors the sample-complexity claim can break down.","fun_headline_variants_meta":{"raw":{"variants":["Reachability sampling: exponential cost is unavoidable","Sampling reachable sets: curse of dimensionality, proven","Exponential sample complexity for reachable sets, no escape","Matching bounds: reachability sampling is inherently exponential","You can't beat exponential sampling for reachable sets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000188,"raw_usage":{"total_tokens":1215,"prompt_tokens":839,"completion_tokens":376,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":583,"completion_tokens_details":{"reasoning_tokens":313}},"tokens_in":583,"tokens_out":376,"duration_ms":4359,"temperature":1.0,"reasoning_tokens":313,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T14:54:12.516537+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A counterexample would be an admissible instance in the problem family where some r-ball around a reachable point carries less than the promised probability mass Γ_T(r), despite positive reach, Lipschitz dynamics, and uniform density. One can test this by numerically integrating the flow on a contracting system and checking whether inf_y P_T(B_r(y)∩S_T) stays above ρ 2^{-n} e^{-3nLT} (r/R)^n for all r ≤ e^{LT} r0; if it fails, the upper bound overstates the true sample requirement.","supporting_citations":[],"review_version":1}