{"id":"12dc6482-05b0-478e-8840-dacf955d12d9","arxiv_id":"2601.07674","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A decentralized random-walk learning protocol that lets idle nodes create replacement walkers can survive 'Pac-Man' attacks that probabilistically eat walkers, at the cost of a bounded bias and linear slowdown.","lead":"This paper proposes a decentralized 'create-if-late' (CIL) mechanism: when a node has not seen a random walk for too long, it creates a new one from its last cached copy, so malicious nodes cannot kill all learning tokens. It claims theoretical guarantees that the walk population stays bounded and that random-walk SGD still converges, but to a slightly biased optimum.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3 is internally inconsistent: the stationary distribution of P_chain in Eq. (13) is not the quasi-stationary distribution ν^(ζ) in Eq. (12) on non-regular graphs.","rationale":"The reader's weakest assumption concerns the equivalence between the actual CIL lineage and a single Markov chain with transition (13). I agree this equivalence is unproven and likely false. However, there is an even more basic problem: even if one grants the authors' condensation and accepts (13) as the effective chain, the theorem's claimed limit is not the stationary distribution of that chain. Eq. (12) sets π_chain = ν^(ζ), the QSD/left eigenvector of Q; Eq. (13) defines a row-stochastic matrix whose stationary distribution is something else for non-regular graphs. Appendix C derives the QSD, Appendix D derives the conditional one-step transition; the paper never proves these two objects share the same stationary distribution. Since main contribution (iii) is precisely convergence to the surrogate in (11), this inconsistency is load-bearing. It also explains why the simulations may not reveal the issue: on complete graphs and regular graphs the row sums of Q are constant, so the two distributions coincide; the paper's convergence plots use complete/regular/ER graphs, and ER with p=0.1 is near-regular, masking the discrepancy. A small non-regular diamond graph would expose it. The reader's REJECT verdict is therefore justified, though for a more elementary reason than the non-Markovian lineage jump. The fix would be to decide what the implemented chain's stationary distribution actually is and restate the theorem accordingly; as written, Theorem 3 cannot be correct. The boundedness results (Theorems 1–2) are not affected by this concern.","tokens_in":24772,"tokens_out":11270,"duration_ms":113234,"concrete_test":"Analytically or numerically check consistency of Eqs. (12) and (13) on a small non-regular robustly connected graph, e.g., the 4-node diamond graph with edges 1-2, 2-3, 3-4, 2-4, ζ=1, and uniform random-walk P. Compute the normalized left eigenvector ν of Q and the stationary distribution π_R of R_uv = Q_uv / Σ_w Q_uw. If ν ≠ π_R — as the example above shows — Theorem 3's stated π_chain cannot be the stationary distribution of P_chain. Optionally simulate CIL's chain on this graph and compare the empirical visitation distribution with both candidates to see which is actually approached.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3 identifies the limit sampling distribution π_chain with the quasi-stationary distribution ν^(ζ), the normalized left eigenvector of Q^(ζ) (Eq. 12, Definition 5). But Eq. (13) defines the effective transition matrix P_chain as the row-normalized Q: R_uv = Q_uv / Σ_w Q_uw. The stationary distribution of a row-normalized sub-stochastic matrix is not generally the left eigenvector of Q; it solves π_u Σ_w Q_uw = Σ_w π_w Q_wu, which reduces to the QSD equation only when every row of Q has the same sum. On a non-regular graph these differ. For instance, take the diamond graph with Pac-Man at node 1 and edges 1-2, 2-3, 3-4, 2-4, using the uniform random walk; for ζ=1, Q has row sums (2/3,1,1), the left eigenvector is approximately (0.307,0.347,0.347), while the stationary distribution of row-normalized R is uniform (1/3,1/3,1/3). Thus Theorem 3's stated limit cannot be the stationary distribution of the chain used in its proof. Appendix C derives the QSD via the Yaglom limit; Appendix D derives R via Bayes' rule. These are different objects, and the paper never proves they share a stationary distribution. This is a correctness failure in the paper's central learning guarantee, independent of the additional non-Markovian 'jump-back' issue in how CIL creates children.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies decentralized random-walk (RW) algorithms under a 'Pac-Man' adversary that probabilistically terminates any RW visiting a malicious node. It proposes the CREATE-IF-LATE (CIL) algorithm, in which benign nodes that have not been visited for a threshold number of slots create a new RW from a cached copy of the last visiting RW. The paper claims three properties: no permanent extinction, almost sure boundedness of the RW population, and convergence of RW-SGD to a biased optimum with bounded deviation. Theorems 1 and 2 address population boundedness; Theorem 3 and Proposition 1 claim convergence and bias quantification, with the limiting sampling distribution identified as the quasi-stationary distribution (QSD) of a sub-stochastic transition matrix. The main technical problem is that Theorem 3's limiting distribution is inconsistent with the effective chain transition matrix derived in Eq. (13) and Appendix D.","tokens_in":25220,"tokens_out":9734,"duration_ms":101856,"significance":"The threat model is relevant and the CIL mechanism is a clean, fully decentralized idea. If the convergence theorem were correct, the paper would provide a useful resilience guarantee for RW-based decentralized learning. The population-level results (Theorems 1 and 2) appear plausible and are supported by simulations. However, the central learning guarantee is not established: the paper equates two different mathematical objects — the QSD of the absorbed chain and the stationary distribution of a row-normalized conditional chain — and the effective-chain construction does not correspond to the actual CIL process. Since Theorem 3 is the paper's main theoretical contribution, this is a load-bearing correctness failure rather than a presentation issue.","major_comments":[{"comment":"The theorem identifies the limiting sampling distribution with the QSD ν^(ζ), defined in Definition 5 as the normalized left eigenvector of Q^(ζ). But Eq. (13) and Appendix D define the effective chain transition as P_chain = D^{-1} Q^(ζ), where D is the diagonal matrix of row sums of Q^(ζ), i.e., conditioning a single RW on not being absorbed at the next step. The stationary distribution π of P_chain solves π_v = Σ_u π_u Q_uv / s_u, with s_u = Σ_v Q_uv; this equals the QSD only when all row sums s_u are equal. On non-regular graphs they are not. For example, for ζ=1 on the diamond graph with Pac-Man at node 1 and edges 1-2, 2-3, 3-4, 2-4, the row sums of Q over benign nodes are (2/3, 1, 1); the QSD is approximately (0.363, 0.319, 0.319), while the stationary distribution of the row-normalized chain is uniform (1/3, 1/3, 1/3). Thus the limit in Eq. (12) is not the stationary distribution","section":"§VI, Theorem 3; Eqs. (12)–(13); Appendix D"},{"comment":"The 'effective single RW' construction does not match the CIL mechanism. CIL creates a child at a benign node u after A_u slots without visits, using a cached copy of the last RW that visited u. In general, u is not the node where the parent walk was terminated; the child is born at an earlier position of the parent's trajectory. The paper condenses the waiting period and states in Appendix C that X_{j'}(t_u + A_u) = u 'degenerates to' X_{j'}(t_u) = u. This erases the state jump from the death node back to u and makes the child appear before the parent's death in the condensed timeline. Consequently, the parent-child lineage is not a time-homogeneous Markov chain with transition matrix (13), and the equality ξ_{s;t} = ξ_{0;t} in Eq. (31) is not derived from the CIL rule. The assertion in Section VI that 'at least one infinite parent-child chain must almost surely exist' is also stated wi","section":"§VI, Definition 6; Appendix C"},{"comment":"The proof of the constant-stepsize bound is not given. Appendix E says it follows from [41, Theorem 1] with substitutions and by 'artificially condensing' time intervals, but it does not verify that the hypotheses of [41] hold for the CIL chain, nor does it derive the displayed constants. Since Proposition 1(2) is part of the claimed bias characterization of the learning algorithm, this is a missing derivation, not just an omitted routine step. The authors should either supply the full argument or state the result as conditional on the cited theorem's assumptions being checked for the CIL process.","section":"§VI, Proposition 1(2); Appendix E"}],"minor_comments":[{"comment":"The proof states that the restricted transition matrix Q^(ζ) is 'reducible and aperiodic' on the transient states, while Definition 4 and the preceding sentence say it is irreducible. This appears to be a typo; the word should be 'irreducible'.","section":"Appendix C, Lemma 3"},{"comment":"Typo: 'Pac-Mac' should be 'Pac-Man'.","section":"Appendix A, Corollary 2"},{"comment":"Typo: 'π^(ζ)_chian' should be 'π^(ζ)_chain' in the statement of Proposition 1.","section":"§VI, Proposition 1"},{"comment":"Typo: 'publich' should be 'public'.","section":"Fig. 11 caption"},{"comment":"The simulation setup says 'We set both the forking and termination probabilities to 1'; the word 'forking' should be 'creation' to match CIL terminology. Also, the empirical curves in Figs. 9–11 primarily demonstrate convergence of loss; they do not directly validate the specific QSD claim in Eq. (12), which is the part of the theory that needs the most support.","section":"§VII-A"}],"recommendation":"reject","confidential_remarks":"The central convergence theorem (Theorem 3) is internally inconsistent: the stationary distribution of the row-normalized chain in Eq. (13) is not the QSD ν^(ζ) in Eq. (12) on non-regular graphs, and the effective-chain construction does not correspond to CIL's cached-copy creation rule. The population boundedness results (Theorems 1 and 2) may be salvageable, but the learning guarantee as stated would require a substantially different proof and a different limiting distribution. This is not a local fix, so I recommend rejection despite the interesting threat model and the clean CIL concept."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new thing here is the create-if-late idea: a fully decentralized, parameter-estimation-free way to keep a population of random walks alive under a probabilistic termination attack. That is a real alternative to DECAFORK's duplication, and the paper deserves credit for the drift-based population analysis. Theorem 1's supermartingale argument looks plausible, and Theorem 2's scaling on complete graphs is a reasonable heuristic with supporting numerics. If the paper were only about population stability, I would be fairly positive.\n\nThe soft spot is the learning convergence guarantee. Theorem 3 claims RW-SGD converges to the minimizer under the quasi-stationary distribution nu^(zeta), the left eigenvector of Q^(zeta). But the effective transition matrix defined in Eq. (13) is the row-normalized Q, whose stationary distribution is not generally the QSD. The stress-test's diamond-graph counterexample is correct: for non-regular row sums, the left eigenvector and the stationary distribution of the row-normalized chain differ. So the paper's own equations are internally inconsistent.\n\nThere is a second, more conceptual problem the paper does not address. In CIL, a child is created at a benign node that has not been visited for A_u slots, using a cached copy of the last visitor. That node is generally not where the parent died, so the lineage can jump backward to an earlier position. The effective process is not the single random walk conditioned on survival, and condensing waiting times does not make it one. The chain is non-Markovian with memory. The existence of an infinite chain is asserted without proof, and even if that is salvageable, the claimed limiting distribution is not derived for the actual process.\n\nAlso, Algorithm 1's pseudocode has a real bug: when a node is not visited and the elapsed time is within threshold, it increments the last-visit counter, so the counter tracks t and the threshold is never exceeded. The text description makes the intended behavior clear, but as written the algorithm would not create RWs. That is fixable, but it is exactly the kind of disconnect that makes the theory hard to trust.\n\nReader's take: the convergence theorem is load-bearing and wrong. The population results stand on their own and the attack model is sensible. I would engage with this paper because the mechanism is worth repairing, but the current version is not accept-shaped. Send to peer review if you want to force the authors to fix the math; otherwise desk-reject and point them to the counterexample.","headline":"The CIL mechanism and population-boundedness results are worth taking seriously, but Theorem 3's convergence claim is mathematically wrong as stated, and the algorithm's pseudocode doesn't match the analyzed rule.","tokens_in":595,"tokens_out":748,"would_cite":false,"duration_ms":70008,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J10","68W15","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a decentralized create-if-late rule lets random-walk learning survive a stealthy node that probabilistically eats every walk that visits it, converging with a quantifiable bias.","keywords":["random walk","decentralized learning","Pac-Man attack","Create-If-Late","self-creating random walks","quasi-stationary distribution","RW-SGD convergence","adversarial termination"],"falsifier":"Run CIL on a small graph with ζ=1 and A large, track one lineage for a long time, and compare the empirical transition frequencies between benign nodes to the row-normalized Q^(1); also compare the lineage's stationary distribution to ν^(1). A statistically significant mismatch—especially on a graph where the cache location differs from the parent's death location—would refute the claimed effective-chain model.","tokens_in":24685,"feed_emoji":"👾","tokens_out":5731,"duration_ms":52169,"temperature":0.7,"pith_summary":"The paper considers decentralized learning in which model updates travel as random-walk tokens on a network, and a single malicious node—the 'Pac-Man'—silently terminates any walk that visits it, so eventually every walk dies and learning halts with no alarm raised. The paper proposes Create-If-Late (CIL): each benign node creates a new walk, copying the last walk that visited it, whenever no walk has visited for a preset number of time slots. The main claim is that CIL guarantees the walk population never becomes permanently extinct, stays almost surely bounded, and lets random-walk stochastic gradient descent converge to a biased optimum, with the bias explicitly bounded and with at most linear slowdown. If correct, this gives a fully decentralized, parameter-estimation-free defense against a stealthy termination adversary.","feed_headline":"Local timeout rule keeps random-walk learning alive under attack","feed_subtitle":"A node that silently eats visiting tokens can only slow learning linearly and shift the final model by a bounded bias.","key_machinery":"The central object is the parent–child chain of random walks and its effective transition matrix [P_chain]_{uv} = Q^(ζ)_{uv} / Σ_v Q^(ζ)_{uv}, the row-normalized sub-stochastic matrix of the absorbed chain on benign nodes. CIL's creation rule—replicate the cached last visitor at any benign node that has gone A_u slots unvisited—supplies the infinite lineage that this chain describes; the quasi-stationary distribution ν^(ζ) (normalized leading left eigenvector of Q^(ζ)) is the stationary distribution of that chain and drives the learning bias. The boundedness results rest on a d-step drift inequality E[Z_{t+d} − Z_t | F_t] ≤ −cζ Z_t + (N−1)d, where d is the maximum time to reach the Pac-Man n","core_discovery":"Under CIL, each parent–child lineage of random walks can be condensed into a single effective random walk whose transition matrix is the row-normalized sub-stochastic matrix Q^(ζ), obtained by restricting the walk to benign nodes and removing the absorbing edge to death. The limiting distribution of this effective walk is the quasi-stationary distribution ν^(ζ) of the absorbed Markov chain—the leading left eigenvector of Q^(ζ). Consequently RW-SGD converges to the minimizer of a surrogate objective that samples benign nodes according to ν^(ζ), and the distance from this biased optimum to the true optimum is bounded by (1/μ)∥∇f(x̃*)∥. In addition, the walk population is almost surely bounded","pith_inferences":["The CIL rule is a generic 'timeout-and-recreate' primitive: any token-passing distributed algorithm that can lose tokens silently—consensus, data collection, monitoring—could use local idle time to re-spawn tokens without needing to count them; the paper's drift argument suggests a design checklist for stable population control in such systems.","The proof treats the lineage as a memoryless chain, but the actual CIL creation jumps back in time to a cached copy at the waiting node; this is the main residual risk. A stress test would compare the empirical transition behavior along real CIL lineages with the row-normalized Q^(ζ).","The bias characterization could be inverted into a detection heuristic: if the final model deviates from what the known stationary distribution would produce, the network can infer that some node is absorbing walks, without labeling any node.","The paper's population results suggest a practical tuning strategy: set the creation probability small enough that expected walk count is O(1) in network size, making communication overhead scale gracefully, while keeping the threshold A small enough that revival delay after extinction stays bounded."],"forward_implications":["Decentralized learning with random walks can tolerate a stealthy walk-terminating adversary using only local visit timestamps, with no centralized detection, no replication, and no estimation of the number of live walks.","The final model is provably biased: it solves a surrogate problem that samples benign nodes according to the quasi-stationary distribution ν^(ζ); as the termination probability ζ tends to 0, this distribution approaches the original sampling distribution and the bias vanishes.","The expected peak number of walks can be made independent of network size by choosing the creation probability q = Θ(1/N^2) on complete graphs, and remains bounded on all graphs.","Temporary extinctions slow learning by at most a constant factor: the expected number of completed gradient steps up to time t is at least (N/ζ)/(N/ζ + A − 1 + 1/q) · t, so convergence is linear in clock time despite interruptions."],"fun_headline_variants":["Self-creating random walks foil silent Pac-Man attacks","CIL algorithm keeps random-walk learning alive under attack","Bounded bias and linear delay: random walks survive Pac-Man","Random walks that fight back: CIL defeats Pac-Man attacks","Under Pac-Man attack, self-created walks keep SGD converging"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The convergence theorem hinges on treating each parent–child lineage as one memoryless random walk with transition matrix equal to the row-normalized sub-stochastic matrix; in the real algorithm, a new walk is born at a node that has waited too long, using a cached copy from an earlier visit, which can jump backward and give the lineage memory—if that equivalence breaks, Theorem 3 no longer describes the implemented rule.","fun_headline_variants_meta":{"raw":{"variants":["Self-creating random walks foil silent Pac-Man attacks","CIL algorithm keeps random-walk learning alive under attack","Bounded bias and linear delay: random walks survive Pac-Man","Random walks that fight back: CIL defeats Pac-Man attacks","Under Pac-Man attack, self-created walks keep SGD converging"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000687,"raw_usage":{"total_tokens":2960,"prompt_tokens":759,"completion_tokens":2201,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":503,"completion_tokens_details":{"reasoning_tokens":2118}},"tokens_in":503,"tokens_out":2201,"duration_ms":16718,"temperature":1.0,"reasoning_tokens":2118,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T11:01:50.793303+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run CIL on a small graph with ζ=1 and A large, track one lineage for a long time, and compare the empirical transition frequencies between benign nodes to the row-normalized Q^(1); also compare the lineage's stationary distribution to ν^(1). A statistically significant mismatch—especially on a graph where the cache location differs from the parent's death location—would refute the claimed effective-chain model.","supporting_citations":[],"review_version":1}