{"id":"8b278cde-374d-44a1-9547-64495e1ae10e","arxiv_id":"2505.18300","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Replacing the target μ by a history-adjusted target μ(x/μ)^{-α} in any graph MCMC sampler gives O(1/α) variance reduction at constant per-step cost, and extends to non-reversible chains.","lead":"This paper presents a way to make random-walk sampling on networks faster and cheaper: instead of changing the walk's step kernel, it changes the sampling target each step based on which nodes have been visited too often or too rarely. The method keeps the mathematical guarantee of targeting the original distribution and works with advanced non-reversible samplers, which the previous kernel-based approach could not handle.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Uniform Poisson-equation bounds (Fort's B2) are asserted, not verified, for non-reversible augmented-state kernels; the spectral gap of P[x] could shrink near the simplex boundary, invalidating the CLT formula (10) for MHDA/2-cycle.","rationale":"I agree with the reader that the load-bearing assumption is the stochastic-approximation regularity of the controlled kernel P[x], specifically Fort's uniform Poisson-equation bounds. The paper's Appendix E.3 handles the augmented-space mismatch by defining Φ(x,i,j)=H(x,i), but it does not verify the uniform bound on the augmented fundamental matrix. This is not a fatal flaw — the condition is plausible and likely holds for small α — but it is precisely the condition that could fail for large α or near the boundary, and it is only asserted, not established. The cost-based comparison with SRRW and the reversible-sampler results are secondary; the CLT variance reduction for non-reversible samplers is the central novelty. My proposed check directly tests both the uniform spectral-gap condition and the end-to-end CLT formula. If the check passes, the CONDITIONAL verdict can be upgraded to acceptance; if it fails, Theorem 3.3 as stated for non-reversible augmented samplers needs qualification. The reader's weakest_assumption identifies the same general area, but I focus on the augmented-state non-reversible case and propose a sharper, quantitative test, hence partial agreement.","tokens_in":36376,"tokens_out":18576,"duration_ms":188171,"concrete_test":"On the cycle graph C_8 with uniform target μ, implement the MHDA augmented kernel P[x] (Algorithm 3 with π[x] in place of μ). Vary x along a line from μ toward the boundary, e.g., x(t) = (1-t)μ + t e_1 for t ∈ {0, 0.1, ..., 0.9} with e_1 the point mass at node 1, renormalized to stay interior. For each x, compute the second-largest eigenvalue modulus of P[x] and the norm of (I - P[x] + 1π[x]^T)^{-1}. If the norm grows by more than 10x as t goes from 0 to 0.9 while the chain remains ergodic, the uniform bound (30) is suspect. Then run HDT-MHDA with α=5 for n=10^6 steps on the same graph and compare the empirical covariance of √n(x_n - μ) to V_base/(2α+1), where V_base is the covariance of vanilla MHDA targeting μ; a deviation beyond the Monte Carlo standard error would indicate that (10) fails for non-reversible augmented samplers.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 3.3 rests on Theorem E.1, condition (B2) (Appendix E.1): for every compact C inside the simplex, the Poisson solution m_x(i) = [(I - P[x] + 1π[x]^T)^{-1}(H(x,·)-h(x))](i) must satisfy sup_{x∈C,i} ‖m_x(i)‖² < ∞ and the continuity bound (31). The paper asserts this follows from continuity of P[x] in x, but for non-reversible samplers on augmented state spaces (MHDA, 2-cycle), P[x] lives on X × Y and the fundamental matrix norm is controlled by the spectral gap of the augmented kernel. No uniform lower bound on this gap is provided over the set of x visited by the SA recursion. Assumption 1 only keeps x_n in the open simplex, not away from the boundary; as x approaches ∂Σ, π[x] ∝ μ_i(x_i/μ_i)^{-α} becomes extremely concentrated on under-visited states and the augmented chain can become nearly trapped, making ‖(I - P[x] + 1π[x]^T)^{-1}‖ diverge. If this happens for x-values the algorithm visits with non-negligible probability, the asymptotic covariance in (10) — and with it the central O(1/α) variance-reduction claim for non-reversible samplers — is not justified. The reversible MH case is safer because the acceptance-rejection kernel's gap is continuous and bounded away from zero on compact subsets of the interior, but the paper's headline compatibility with 'any' non-reversible MCMC sampler is exactly where the unverified step lies.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a history-driven target (HDT) framework for MCMC on finite discrete state spaces (graphs). Instead of modifying the transition kernel as in the self-repellent random walk (SRRW), HDT replaces the target distribution μ by a history-dependent target π[x] ∝ μ_i (x_i/μ_i)^{-α}, where x is the empirical visit measure. Any base reversible or non-reversible MCMC sampler can be run with this adaptive target, and the empirical measure is updated after each draw. The main theoretical claims are: a.s. convergence of x_n to μ (Theorem 3.3(a)), a CLT with covariance V_HDT(α)=V_base/(2α+1) (Theorem 3.3(b)), and a cost-based CLT/Lemma 3.6 showing an advantage over SRRW under a fixed compute budget. Experiments on several real-world graphs with MH, MTM, MHDA, and 2-cycle samplers show consistent TVD/NRMSE improvements, and an LRU cache is introduced for memory reduction in large graphs.","tokens_in":36782,"tokens_out":13337,"duration_ms":103982,"significance":"If the theoretical claims hold, this is a significant and useful contribution: it offers a universal, cheap variance-reduction wrapper that extends the self-repellent mechanism to non-reversible and augmented-state MCMC samplers, with an elegantly derived 1/(2α+1) covariance reduction. The cost-based comparison with SRRW under a fixed budget is practically important, and the experimental validation is extensive. However, the proof of the central CLT for non-reversible augmented-state samplers has a gap in the verification of the stochastic-approximation conditions; the universality claim is therefore not yet fully established. The linear-algebra derivation of the covariance itself is correct and the ODE stability proof is sound.","major_comments":[{"comment":"The verification of condition (B2) of Theorem E.1 is incomplete. Equation (30) requires sup_{x∈C,i} ||m_x(i)||^2 < ∞ for every compact C, but the proof only shows pointwise finiteness of the fundamental matrix for each x∈Int(Σ). Assumption 1 only guarantees x_n∈Int(Σ), not that the trajectory lies in a compact subset of Int(Σ) bounded away from the boundary; the update (2) lets components decay as O(1/n). For x approaching ∂Σ, π[x] becomes extremely concentrated and the spectral gap of P[x] may shrink, making (I−P[x]+1π[x]^T)^{-1} unbounded. The reference to truncation devices in Doshi et al. (2023, Remark 4.5 and Appendix E) is not implemented or analyzed for Algorithm 1, so the CLT formula (10) is not justified for the claimed class of non-reversible samplers.","section":"Appendix E.1"},{"comment":"The extension to non-reversible augmented-state samplers (MHDA, 2-cycle) replaces H by Φ on X×Y, but the required uniform bounds on the augmented fundamental matrix are exactly the missing control. The proof asserts continuity of P[x] in x and claims this suffices for Fort's condition (31); however, continuity on the non-compact domain Int(Σ) does not yield a uniform modulus over the set actually visited by the SA recursion, which may approach the boundary. For MHDA and the 2-cycle chain, the kernel is piecewise defined or depends on the auxiliary state, and the spectral gap may vanish near ∂Σ. Thus the proof does not establish Theorem 3.3(b) for these samplers, which is the paper's headline claim of compatibility with non-reversible MCMC.","section":"Appendix E.3"}],"minor_comments":[{"comment":"In the final step of the proof of Lemma 3.1, the condition '1 − ρ2 ≤ 1' appears to be a typo; to derive α ≥ 0 from C4 the intended condition is 1−ρ2 < 0. As written, the derivation is logically incomplete.","section":"Appendix B"},{"comment":"The 'if and only if' statement assumes differentiability of f in the proof, while C2 only requires continuity. Either C2 should be strengthened to 'continuously differentiable' or the proof should be adapted to the weaker condition.","section":"Lemma 3.1"},{"comment":"The step size in the empirical-measure update is 1/(n+1) in Eq. (2) but 1/(n+2) in Eq. (35). The indexing should be made consistent.","section":"Section 2 / Appendix E"},{"comment":"Step 5 has a typo: 'Stpe' should be 'Step'.","section":"Algorithm 2"},{"comment":"The phrase 'unbiased samples' is imprecise for MCMC; use 'asymptotically unbiased' or 'consistent' to avoid confusion with finite-sample unbiasedness.","section":"Abstract"},{"comment":"The list T = {3000, 15000, 15000, 3000} is not explicitly matched to the four graphs; please specify the correspondence.","section":"Appendix H.1"},{"comment":"Equation (15) for the LRU cache is heuristic; a brief explanation of why the neighbor-average approximates the missing frequency would improve readability.","section":"Section 4.5"},{"comment":"The assumption that the base kernel P is full-rank is not needed for formula (4) and excludes some ergodic chains with zero eigenvalues; consider restating the condition as 'ergodic and aperiodic'.","section":"Section 2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within the scope of the journal. The core idea is compelling and the experiments are thorough. My main concern is the proof gap in the verification of Fort's conditions for non-reversible augmented-state samplers; if the authors can supply a rigorous truncation argument or otherwise establish the uniform bounds, or restrict Theorem 3.3 to the reversible case and treat non-reversible samplers as an empirical extension, the paper would be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick read: this paper does something real. It takes the self-repellent idea from SRRW and moves the history dependence from the kernel into the target distribution: pi_i[x] proportional to mu_i (x_i/mu_i)^{-alpha}. That sounds like a small change, but it makes the method compatible with non-reversible samplers and drops the per-step O(degree) normalization cost of SRRW. The central result, Theorem 3.3, gives almost-sure convergence of the empirical measure to mu and a CLT with covariance V_base/(2alpha+1). I checked the linear algebra: the drift Jacobian at mu is alpha-mu-1^T - (alpha+1)I, the e^{alpha t} terms cancel because 1^T U = 0, and the 1/(2alpha+1) factor falls out cleanly. The cost-based comparison with SRRW (Lemma 3.6) also holds; it is a nice way to make the computational advantage quantitative. The experiments on Facebook, Gnutella, and the non-uniform target graphs are consistent with the theory, and the LRU cache is a sensible engineering add-on.\n\nThe soft spot is the stochastic-approximation proof for non-reversible samplers on augmented state spaces (MHDA, 2-cycle). Condition (B2) of the SA theorem requires uniform bounds on solutions to the Poisson equation for the controlled kernel P[x] over compact sets. The paper asserts that continuity of P[x] in x gives these bounds, but for an augmented kernel the fundamental matrix norm is governed by the spectral gap, and no uniform lower bound is provided. Since the target pi[x] becomes extremely concentrated as x approaches the simplex boundary, the gap could shrink. This is not a fatal flaw: because x_n converges to mu in the interior, a local CLT argument or a restriction to a compact neighborhood of mu should close the gap. But as written, the proof for the headline compatibility with 'any' non-reversible sampler is incomplete.\n\nMinor issues: the abstract says 'near-zero variance', which overstates an O(1/alpha) asymptotic result; the axioms C2/C4 are chosen to produce exactly the power-law target, so the 'iff' in Lemma 3.1 is partly by construction (though the axioms themselves are natural); no code is shipped; the LRU cache is heuristic without theory.\n\nBottom line: this deserves a serious referee. It is a solid incremental advance with a correct core derivation and useful experiments, but the SA regularity conditions for non-reversible samplers need a rigorous fix before publication.","headline":"A real upgrade to self-repellent graph sampling that moves history dependence into the target and gets a clean V_base/(2alpha+1) CLT; the one genuine gap is an unproven SA regularity condition for non-reversible augmented samplers.","tokens_in":37342,"tokens_out":6588,"would_cite":true,"duration_ms":58289,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J22","60F05","62M05","65C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proposes a history-driven target framework: replace the MCMC target $\\boldsymbol{\\mu}$ with $\\pi_i[\\mathbf{x}] \\propto \\mu_i (x_i/\\mu_i)^{-\\alpha}$, and proves the empirical measure still converges almost surely to…","keywords":["history-driven target","Markov chain Monte Carlo","graph sampling","self-repellent random walk","non-reversible Markov chains","stochastic approximation","variance reduction","LRU cache"],"falsifier":"Run HDT-MCMC on a graph with a known spectral gap, such as a barbell graph with Metropolis-Hastings, and compare the empirical covariance of $\\sqrt{n}(\\mathbf{x}_n - \\boldsymbol{\\mu})$ at large $\\alpha$ and large $n$ against $V^{\\mathrm{base}}/(2\\alpha+1)$; if the ratio drifts with $n$ or the CLT fails to stabilize for $\\alpha = 10$ with $n = 10^8$, the continuity or Poisson-equation assumption is violated.","tokens_in":36135,"feed_emoji":"🎲","tokens_out":7580,"duration_ms":51809,"temperature":0.7,"pith_summary":"This paper establishes that self-repellent exploration in MCMC can live in the target distribution rather than the transition kernel. It designs a history-driven target $\\pi_i[\\mathbf{x}] \\propto \\mu_i (x_i/\\mu_i)^{-\\alpha}$, indexed by the empirical visit measure $\\mathbf{x}$, and proves that any base sampler run against this adaptive target still converges almost surely to the original target $\\boldsymbol{\\mu}$. The central payoff is Theorem 3.3: the sampler's asymptotic covariance is divided by $2\\alpha+1$, so variance approaches zero as $\\alpha$ grows, at the same $O(1)$ per-sample cost as ordinary Metropolis-Hastings. Because only the target changes, both reversible and non-reversible samplers plug in, and a cost-based CLT shows HDT beats the self-repellent random walk under a fixed budget whenever the average expanded degree exceeds 2. A heuristic LRU cache makes the scheme feasible on large graphs by tracking only a fraction of visit counts.","feed_headline":"A history-driven target shrinks MCMC variance by 2α+1","feed_subtitle":"Replacing the sampler's target with a history-weighted one keeps estimates unbiased while shrinking variance and per-step cost.","key_machinery":"The load-bearing object is the history-driven target $\\pi_i[\\mathbf{x}] \\propto \\mu_i (x_i/\\mu_i)^{-\\alpha}$, whose unnormalized form $\\tilde{\\pi}_i = \\tilde{\\mu}_i (\\tilde{x}_i/\\tilde{\\mu}_i)^{-\\alpha}$ depends only on the current state's visit count and target weight, not on neighbors. Lemma 3.1 proves Conditions C1–C4 (scale invariance, local dependence, fixed point at $\\boldsymbol{\\mu}$, history dependence) force exactly this power-law form. The analysis treats the empirical measure recursion as stochastic approximation with mean field $h(\\mathbf{x}) = \\pi[\\mathbf{x}] - \\mathbf{x}$ and ODE $\\dot{\\mathbf{x}} = \\pi[\\mathbf{x}] - \\mathbf{x}$; the Lyapunov function $V(\\mathbf{x}) = \\sum_i \\mu_i (x_i/\\mu_i)^{-\\alpha}$ establishes global asymptotic stability of $\\boldsymbol{\\mu}$, and the Jacobian $\\nabla h(\\boldsymbol{\\mu}) = \\alpha \\boldsymbol{\\mu}\\mathbf{1}^T - (\\alpha+1)I$ produces the factor $1/(2\\alpha+1)$ in the covariance.","core_discovery":"The central claim is Theorem 3.3: for any ergodic base MCMC sampler whose kernel $P[\\mathbf{x}]$ targets $\\pi[\\mathbf{x}] \\propto \\mu_i (x_i/\\mu_i)^{-\\alpha}$, the HDT update $\\mathbf{x}_{n+1} = \\mathbf{x}_n + \\frac{1}{n+1}(\\delta_{X_{n+1}} - \\mathbf{x}_n)$ satisfies $\\mathbf{x}_n \\to \\boldsymbol{\\mu}$ almost surely and $\\sqrt{n}(\\mathbf{x}_n - \\boldsymbol{\\mu}) \\rightsquigarrow \\mathcal{N}(0, V^{\\mathrm{base}}/(2\\alpha+1))$, where $V^{\\mathrm{base}}$ is the base sampler's limiting covariance when it targets $\\boldsymbol{\\mu}$ directly. The proof works for non-reversible samplers on augmented state spaces by defining the empirical measure only on the original space and using the marginal stationary distribution, something the SRRW construction cannot do because its kernel modification requires detailed balance. A companion cost-based CLT (Lemma 3.6) gives $C_{\\mathrm{HDT}} V_{\\mathrm{HDT}}(\\alpha) \\preceq (2/\\mathbb{E}_{i\\sim\\mu}[|N(i)|]) \\, C_{\\mathrm{SRRW}} V_{\\mathrm{SRRW}}(\\alpha)$, so the advantage grows with average degree.","pith_inferences":["Beyond the paper, the same target-replacement trick could apply to continuous or very high-dimensional state spaces where enumerating neighbors is impossible, because the acceptance ratio only needs the two local pairs $(x_i,\\mu_i)$ and $(x_j,\\mu_j)$.","The LRU experiments suggest the empirical measure can be approximated by temporal locality; a testable question is whether a streaming frequency sketch preserves the $1/(2\\alpha+1)$ covariance constant or degrades it by a known factor.","The cost-based comparison implies HDT's value is largest when neighbor enumeration is expensive, such as dense graphs, high-degree nodes, or rate-limited graph APIs, and minimal on low-degree structures like paths where $\\mathbb{E}[|N(i)|]$ is near 2.","If the same Lyapunov structure transfers to continuous target densities, HDT could reduce variance in high-dimensional MCMC without gradient information."],"forward_implications":["Every base sampler, reversible or not, inherits a $1/(2\\alpha+1)$ contraction of its asymptotic covariance while remaining unbiased for $\\boldsymbol{\\mu}$.","Variance orderings between samplers are preserved: if sampler A beats sampler B in covariance, HDT-A beats HDT-B at every $\\alpha$.","Under a fixed compute budget, HDT's cost-scaled covariance is at most $2/\\mathbb{E}[|N(i)|]$ times SRRW's, so the advantage widens as average degree grows.","The framework admits non-reversible samplers such as MHDA and 2-cycle chains, which SRRW cannot use.","With an LRU cache holding about 10% of the visit counts, HDT-MHRW still beats the base sampler in total variation distance."],"supporting_citations":[{"why":"Supplies the SRRW baseline, its kernel (1), and the variance formula (5) that HDT is designed to beat.","marker":"Doshi et al. (2023)"},{"why":"Provides the stochastic-approximation CLT for controlled Markov chains used to prove Theorem 3.3.","marker":"Fort (2015)"},{"why":"Gives the almost-sure convergence and CLT theorems for decreasing-gain stochastic approximation that the proof invokes.","marker":"Delyon (2000)"},{"why":"Defines the MHDA non-reversible sampler used in experiments and in the augmented-state-space adaptation argument.","marker":"Lee et al. (2012)"},{"why":"Supplies the random-change-of-time theorem that converts the time-based CLT into the cost-based CLT.","marker":"Billingsley (2013)"},{"why":"Defines the locally balanced multiple-try Metropolis sampler used as a reversible base chain in the simulations.","marker":"Chang et al. (2022)"}],"fun_headline_variants":["History-driven target cuts MCMC cost and variance on any graph","Replace the target, not the kernel: HDT speeds MCMC on graphs","Non-reversible MCMC gets history boost with lightweight target swap","MCMC sampler upgrade: history-dependent target beats self-repellent kernels","Graph sampling with near-zero variance minus the kernel overhead"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The result depends on the base sampler's kernel $P[\\mathbf{x}]$ being continuous in $\\mathbf{x}$ and satisfying uniform Poisson-equation bounds for the stochastic-approximation CLT; for non-reversible or augmented-state samplers this is asserted rather than verified, and if the chain's mixing slows dramatically as $\\pi[\\mathbf{x}]$ concentrates, the variance reduction would require impractically many samples.","fun_headline_variants_meta":{"raw":{"variants":["History-driven target cuts MCMC cost and variance on any graph","Replace the target, not the kernel: HDT speeds MCMC on graphs","Non-reversible MCMC gets history boost with lightweight target swap","MCMC sampler upgrade: history-dependent target beats self-repellent kernels","Graph sampling with near-zero variance minus the kernel overhead"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00115,"raw_usage":{"total_tokens":4841,"prompt_tokens":1089,"completion_tokens":3752,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":705,"completion_tokens_details":{"reasoning_tokens":3663}},"tokens_in":705,"tokens_out":3752,"duration_ms":24826,"temperature":1.0,"reasoning_tokens":3663,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:36:57.313714+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run HDT-MCMC on a graph with a known spectral gap, such as a barbell graph with Metropolis-Hastings, and compare the empirical covariance of $\\sqrt{n}(\\mathbf{x}_n - \\boldsymbol{\\mu})$ at large $\\alpha$ and large $n$ against $V^{\\mathrm{base}}/(2\\alpha+1)$; if the ratio drifts with $n$ or the CLT fails to stabilize for $\\alpha = 10$ with $n = 10^8$, the continuity or Poisson-equation assumption is violated.","supporting_citations":[],"review_version":1}