{"id":"7d8b67f2-8e18-4d2a-a6e2-9e0e76468f73","arxiv_id":"2505.20296","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Six current reasoning LLMs, including commercial systems, exhibit structured-search failures on verifiable computation tasks and degrade as the solution space grows.","lead":"Reasoning AI models spend extra thinking time but wander through the solution space, making invalid steps, revisiting old paths, and sometimes inventing conclusions. The paper formalizes what a structured reasoning process should look like and shows that no current model meets that standard on the tasks tested.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Fixed command grammar may cause the wandering it measures; without a free-form CoT control, the universal claim is unsupported.","rationale":"The reader's weakest assumption is correct and is the single biggest threat to the paper's central claim. The qualitative observations in Appendix D are genuine demonstrations that models, when compelled to emit structured commands, make invalid steps, loop, backtrack wrongly, and mis-summarize. However, those observations cannot distinguish intrinsic wandering from grammar-induced error. The quantitative coverage curves in Fig. 6 use the same protocol, and the closed-source models are run once with no error bars, so the universal inference rests on a single measurement instrument. Eq. (1) does not help: it assumes wandering and then shows degradation, so it is illustrative rather than evidential. The paper is honest about limitations in Appendix B (additional failure modes likely exist, some patterns hard to define), but it does not flag the format confound. A free-form CoT control with post-hoc parsing would settle the question. If the control shows comparable wandering, the claim stands; if not, the conclusion must be restricted to constrained-format reasoning. The vacuous necessity definition is a further formal weakness that should be fixed by requiring a proper subsequence or an alternative condition, but it is secondary. This is not a fabrication concern; the transcripts look credible and detailed. Verdict remains conditional pending the control experiment.","tokens_in":67012,"tokens_out":5748,"duration_ms":60653,"concrete_test":"Re-run the core quantitative task (Permutation with Duplicates) and one qualitative task (24 Game) on all six models under two conditions: (A) the original constrained command format; (B) unconstrained free-form CoT with identical token budgets, then parse (B) traces into the same state-space audit format using a fixed rule-based parser (or a second LLM with a detailed rubric). Compare coverage ratios, invalid-step rates, revisitation rates, and premature-termination rates across conditions. If condition (B) shows materially higher coverage or slower degradation with problem size, the constrained format is driving the wandering and the paper's conclusion is a measurement artifact.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing assumption is that the Section 3 audit format—the CHECK/ATTEMPT/BACKTRACK/STATE/MERGE command grammar enforced in prompts—does not distort the reasoning process being measured. The paper's universal empirical claim (Section 4.4, Fig. 6) and all qualitative case studies (Appendix D) are generated under this protocol, yet there is no free-form chain-of-thought control condition. RLLMs are trained on natural-language reasoning; forcing them to emit a fixed symbolic grammar may itself produce invalid steps (e.g., the backtracking error in D.3), premature termination (D.2), state revisitation (D.4), and unfaithful summaries (D.8). The authors never test whether the same models, allowed to reason freely and then parsed post hoc into the same state space, would exhibit less wandering. If the format is an intervention, the central claim is not supported by the data as presented. Secondary internal issue: the necessity condition in Definition 2 is vacuous as written—choosing J'=J leaves an empty valid trace with fewer goal states, so every state of an effective trace counts as 'necessary'—but this is less central than the measurement artifact.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper argues that current reasoning LLMs (RLLMs) are 'wandering solution explorers' rather than systematic searchers. It formalizes systematic exploration via validity, effectiveness, and necessity, identifies eight failure modes, and presents qualitative case studies on six models across eight structured tasks. A quantitative experiment on a permutation-enumeration task shows solution coverage degrading as problem size grows, supporting the claim that RLLMs wander. The paper concludes that test-time scaling without structural search guarantees leads to competent-looking but shallow reasoning.","tokens_in":67065,"tokens_out":4634,"duration_ms":47473,"significance":"The paper makes a useful contribution by cataloging concrete reasoning failures (boundary violations, procedure omissions, incorrect backtracking, state revisitation, infinite self-loops, state staleness, execution errors, unfaithful conclusions) and by including full, readable trace-level evidence in Appendix D. The qualitative case studies are vivid and demonstrate that, under the imposed protocol, current RLLMs produce invalid steps, revisit states, loop, and mis-summarize their own reasoning. The paper also raises a practically important challenge about the limits of test-time compute. However, the central universal claim that RLLMs are wanderers 'by nature' is not yet supported: all evidence is collected under a fixed command grammar, and the quantitative support comes from a single task. The formal framework in Section 2 also contains a vacuous definition that undermines the stated theory of systematic exploration.","major_comments":[{"comment":"The audit protocol forces all reasoning into a fixed command grammar (CHECK, ATTEMPT, BACKTRACK, MERGE, STATE). No control condition compares this to free-form chain-of-thought with post-hoc parsing. Therefore the invalid steps, premature stops, and repeated states observed in the case studies and quantified in Fig. 6 could be artifacts of the imposed format rather than intrinsic properties of the models' reasoning. The authors should add a free-form CoT control condition or, at minimum, restrict the empirical claim to behavior under the imposed symbolic grammar.","section":"Section 3, Appendix D, Section 4.4"},{"comment":"The necessity condition is vacuous as written. For any state s_ji in a trace J, taking the subsequence J' = J yields an empty remaining trace that contains fewer goal and dead-end states, and the empty sequence satisfies the validity clause vacuously. Hence every state of any effective trace counts as 'necessary', so the 'unnecessary exploration' failure mode defined in Section 2.3 is not actually characterized by Definition 2(c). The definition needs to be repaired, for example by requiring J' to be a proper subsequence and by specifying that the remaining trace must still be a valid exploration of the same problem.","section":"Definition 2(c), Section 2.3"},{"comment":"The universal claim that 'all reasoning models exhibit wandering characteristics' rests on a single quantitative task, Permutation with Duplicates, with no statistical test and no comparison against a systematic-exploration baseline. The qualitative case studies support the existence of wandering behaviors in eight tasks, but the prevalence and generality of the phenomenon across task types is not quantitatively established. The authors should either provide quantitative coverage or error-rate metrics for multiple tasks, or weaken the concluding claim to 'all models wander on the tested permutation task under the structured-format protocol'.","section":"Figure 6, Section 4.4"}],"minor_comments":[{"comment":"The open-source models are run 10 times and closed-source models only once; Figure 6 shows error bars only for open-source models. The text should state this asymmetry explicitly so readers do not infer similar uncertainty for the closed-source results.","section":"Appendix C.2 / Figure 6"},{"comment":"The task box in D.7 says 'Input: [12, 13, 2, 8]' but the presented problem and ground truth concern the prime factorization of 177750; this appears to be a copy-paste error from the 24 Game section and should be corrected.","section":"Appendix D.7"},{"comment":"The text says 'As shown in Fig. 2' when referring to the performance plateau, but the plateau appears in Figure 1; Figure 2 is the DFS illustration and is not a plot of success probabilities.","section":"Section 2.1"},{"comment":"The word 'deplicate' in the task description should be 'duplicate'.","section":"Section 4.4"},{"comment":"The definition of a dead-end refers to 'unexplored states' in the trace, but 'unexplored' is not formally defined; it would be cleaner to define a dead-end as a state whose all reachable successors are already in the trace.","section":"Definition 1 and Definition 2"}],"recommendation":"major_revision","confidential_remarks":"The paper would be strengthened by repositioning it as an analysis of structured-format reasoning behavior and by adding a control condition. The current title and abstract make a much broader claim about 'reasoning LLMs' that the evidence does not yet fully support. The qualitative appendices are valuable and should be preserved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the case studies in Appendix D are the real contribution: full traces of DeepSeek-R1, QwQ, Sonnet-3.7, and O3 showing invalid backtracking, repeated states, stale cluster states, arithmetic slips, and summaries that don't match the reasoning. That's the best evidence I know of for process-level unreliability. Second, the paper's headline—'reasoning LLMs are wandering solution explorers'—is a lot more general than what the experiments can support. The quantitative claim rests on one task (Permutation with Duplicates), single runs for three models, no error bars for them, and the whole audit is done under a fixed command grammar with no free-form chain-of-thought control. If that grammar is an intervention, the wandering could be partly a measurement artifact.\n\nWhat's genuinely new: the three-part error taxonomy (invalid/unnecessary/evaluation errors), the trace-audit methodology with CHECK/ATTEMPT/BACKTRACE, and the formal definition of systematic exploration. Those are usable even if the formal definition has a flaw: the necessity condition is vacuous as written—removing the whole trace makes any state 'necessary.' The exponential model in Eq. (1) is just a closed-form consequence of its own omission-probability assumption; it illustrates the plateau argument but adds no independent empirical weight.\n\nThe soft spots are proportionate. The format-faithfulness assumption is load-bearing and untested; a free-form CoT control, parsed post hoc into the same state space, is the obvious experiment to run before trusting the universal claim. There are also minor copy-paste errors (Appendix D.7 shows the wrong input; D.8's text attributes the example to Sonnet 3.7 while the figure says DeepSeek-R1). None of this suggests fabrication—the authors are honest in Appendix B about the taxonomy being incomplete.\n\nWho this is for: researchers working on test-time scaling, process reward models, and reasoning evaluation. The taxonomy and traces deserve a serious referee and would probably come out stronger with a narrowed claim or the added control. I'd send it to review.","headline":"A genuinely useful failure-mode taxonomy and the most detailed process-level traces I've seen, but the universal 'wanderer' claim outruns the evidence.","tokens_in":67726,"tokens_out":3185,"would_cite":true,"duration_ms":32438,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Reasoning LLMs are wanderers: despite test-time computation, they do not systematically explore solution spaces, and their solution coverage decays as problem complexity grows.","keywords":["reasoning LLMs","systematic exploration","test-time computation","solution coverage","reasoning trace audit","failure modes","backtracking","process-level evaluation"],"falsifier":"Run the same six models on the same eight tasks without the fixed command grammar, let them reason in free-form natural language, and parse the traces afterward with the same rule-based auditor; if the invalid steps, omissions, and backtracking errors largely vanish, the conclusion that RLLMs are intrinsically wandering explorers would not survive, because the wandering would be an artifact of the imposed format. Alternatively, any model that maintains near-complete solution coverage on permutation enumeration as the solution space grows large would directly contradict the universal claim.","tokens_in":66610,"feed_emoji":"🧭","tokens_out":7303,"duration_ms":74967,"temperature":0.7,"pith_summary":"The paper sets out to show that current reasoning large language models (RLLMs) are wanderers rather than systematic explorers: they produce long reasoning traces at test time, but those traces routinely contain invalid steps, redundant revisits, and unfaithful conclusions, and they do not reliably cover the solution space. The authors formalize systematic exploration as a trace that is valid, effective, and necessary, and then use a controlled audit of six state-of-the-art models on eight computation tasks to show that every model violates these properties. Their quantitative measure, solution coverage on permutation enumeration, declines as the solution space grows for all six models, including the strongest closed-source ones. The stakes are that increasing test-time computation without structural search guarantees will keep producing models that look competent on easy problems yet collapse as problem complexity grows.","feed_headline":"Six reasoning models wander instead of systematically searching","feed_subtitle":"Longer thinking can look competent on easy tasks while collapsing as problem depth grows.","key_machinery":"The load-bearing object is a formal definition of systematic exploration: a trace $J$ satisfies validity, effectiveness, and necessity. To make reasoning auditable, the paper projects problems into structured computational tasks with a fixed command grammar (CHECK, ATTEMPT, BACKTRACK, MERGE, STATE, END) so that each reasoning step can be matched against programmatically generated ground truth. The quantitative argument is carried by a wandering-agent success probability for the depth-first-search problem, $p_s(d,m,q_w)=1-(1-q_w^{d-1})^m$, showing that a wanderer who omits a branch with probability $p_w$ suffers exponentially decaying success as depth $d$ grows, while exhibiting performance plateaus at low $d$ that can mislead evaluations.","core_discovery":"The paper's central claim is that reasoning LLMs, despite test-time computation techniques such as chain-of-thought, tree search, and long reasoning, lack the ability to systematically explore the solution space. The thesis is that a 'better' or systematic solution exploration should satisfy three properties, namely validity (each step respects the problem's reachability structure), effectiveness (at least one goal state is reached), and necessity (every state contributes to reaching a goal or eliminating alternatives), and that none of the six evaluated RLLMs exhibits these properties consistently. Empirically, the paper reports persistent failure modes: boundary violations, procedure omissions, incorrect backtracking, state revisitation, infinite self-loops, state staleness, execution errors, and unfaithful conclusions. On a quantitative testbed, enumerating unique permutations with duplicates, all six models show solution coverage that degrades as the number of valid goal states increases, which the paper interprets as evidence that they are wanderers rather than systematic explorers, with performance that can appear competent on easy problems yet degrade sharply as complexity grows.","pith_inferences":["The exponential-decay formula implies a threshold effect: a model can look near-perfect on benchmarks built from shallow problem instances and fail abruptly once depth crosses a certain point, so benchmarks should report coverage as a function of problem depth rather than only average accuracy.","Because the audit forces a fixed command grammar, a free-form chain-of-thought control condition is needed to confirm that the observed errors are intrinsic to the models rather than induced by the format.","The same process-level metrics, such as invalid steps, revisits, and coverage, could be turned into training rewards or early-exit signals, potentially guiding models toward systematic search without architectural redesign."],"forward_implications":["If the central claim is correct, additional test-time computation will not by itself turn a wandering model into a systematic explorer: larger compute can produce longer traces without better solution-space coverage.","Benchmarks that grade only final answers will overestimate capability, because performance plateaus on easy instances hide the sharp degradation on deeper ones.","Process-level evaluation, such as trace validity, search completeness, and coverage, should become a standard complement to final-answer accuracy for reasoning models.","Architecture and training changes, such as explicit state tracking, backtracking support, and process supervision, would be needed to reach systematic exploration rather than relying on scale alone."],"supporting_citations":[{"why":"Supplies the chain-of-thought paradigm that the paper challenges as insufficient for systematic exploration.","marker":"[24]"},{"why":"Represents tree-of-thoughts-style structured prompting that the paper argues still does not produce systematic exploration.","marker":"[29]"},{"why":"Argues that scaling test-time compute can be effective; this is the hope the paper claims does not guarantee systematic search.","marker":"[16]"},{"why":"Provides one of the six evaluated reasoning models whose traces are audited and found to wander.","marker":"[9]"},{"why":"Provides another evaluated closed-source model whose reasoning traces show errors such as state revisitation.","marker":"[1]"},{"why":"Provides the strongest commercial model in the evaluation, which still exhibits solution-coverage degradation.","marker":"[14]"},{"why":"Provides an open reasoning model whose case-study traces illustrate incorrect backtracking and infinite self-loops.","marker":"[19]"}],"fun_headline_variants":["LLMs are wanderers, not systematic explorers","Systematic search absent in reasoning LLMs","Reasoning LLMs roam, they don't explore systematically","Even with extra thinking, LLMs fail to explore well","Study: LLMs wander instead of systematically seeking"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper's audit assumes that forcing a model to write its reasoning as CHECK, ATTEMPT, BACKTRACK, and similar commands does not itself distort the reasoning and create the errors being measured.","fun_headline_variants_meta":{"raw":{"variants":["LLMs are wanderers, not systematic explorers","Systematic search absent in reasoning LLMs","Reasoning LLMs roam, they don't explore systematically","Even with extra thinking, LLMs fail to explore well","Study: LLMs wander instead of systematically seeking"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00018,"raw_usage":{"total_tokens":1274,"prompt_tokens":886,"completion_tokens":388,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":502,"completion_tokens_details":{"reasoning_tokens":314}},"tokens_in":502,"tokens_out":388,"duration_ms":4980,"temperature":1.0,"reasoning_tokens":314,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:56:37.620267+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same six models on the same eight tasks without the fixed command grammar, let them reason in free-form natural language, and parse the traces afterward with the same rule-based auditor; if the invalid steps, omissions, and backtracking errors largely vanish, the conclusion that RLLMs are intrinsically wandering explorers would not survive, because the wandering would be an artifact of the imposed format. Alternatively, any model that maintains near-complete solution coverage on permutation enumeration as the solution space grows large would directly contradict the universal claim.","supporting_citations":[],"review_version":1}