acceptodds
Under review as a conference paper at ICLR 2027

Active Shortcut Discovery in Shared State Graphs for Foundation Model Reasoning

Abstract

Foundation-model reasoning methods such as Tree of Thoughts and Graph of Thoughts improve over one-shot prompting by searching over intermediate states, but their trajectory-centric representations repeatedly explore equivalent subproblems and make errors costly. We study how such search can be reformulated around a shared AND-OR graph for tasks with reusable Markovian state structure. Equivalent intermediate states are merged within and across problem instances, proof status propagates through the graph, proof-relevant actions are verified before accepting solutions, and our novel Active Shortcut Discovery queries the generator to connect open states to already solved regions. On two challenging LLM reasoning benchmarks, this approach improves Macro-F1 over the strongest baselines by 25.9% on WickedGame24 and 19.6% on PrefixBooleanExpression while using 11.7 times fewer completion tokens. On retrosynthetic planning, it matches state-of-the-art success rates while producing the smallest search graphs. These results show that structured reasoning systems can reduce both redundant computation and hallucinated solutions by reusing verified intermediate states rather than restarting search for each trajectory or instance.

Primary area:
foundation or frontier models, including LLMs
Keywords:
foundation models, reuse, neurosymbolic approaches

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_6gEsOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses two main problems in LLM search-based reasoning: repeatedly solving the same subproblems and making errors that lead to wasted search effort and incorrect answers. The authors organize reasoning into a shared AND-OR graph and introduce Active Shortcut Discovery. The method combines LLM-generated candidate actions with subproblem reuse, structured search, and verification, allowing previous reasoning results to be reused in future problem solving. Experiments show substantial improvements in Macro-F1 on two reasoning benchmarks.

Critical strengths
  1. The problem is clearly defined. The paper distinguishes redundancy within a single problem instance from redundancy across instances, and reuses concrete intermediate results through shared states. This is more direct than storing strategies or prompt templates: the system records how far a subproblem has been explored and whether it has been solved.
  2. Including unsolvable instances strengthens the evaluation. Testing only solvable problems can hide a model’s tendency to produce an answer even when none exists. WickedGame24 and the boolean expression task include unsolvable or malformed inputs, testing both the ability to find correct solutions and to reject invalid instances. In Table 2, the proposed method achieves low rates across all three error categories, which is more informative than overall accuracy alone.
Critical weaknesses
  1. The ablation studies are not comprehensive enough. Table 3 examines verification and shortcut discovery, but the provided sections lack separate ablations of state merging and cross-instance reuse. It remains unclear whether the gains mainly come from verification, a better search strategy, or shared states. Without verification, adding shortcuts reduces token usage but lowers Macro-F1 from 28.3 to 21.9, suggesting that shortcuts depend on reliable intermediate results and may amplify errors.
  2. The comparison involving cross-instance sharing may not be entirely fair. The proposed method shares search results across multiple instances, whereas some baselines mainly solve each instance independently.
Questions for authors
  1. How does the method ensure that all valid actions have been explored, rather than the model failing to propose the correct action or the search budget running out? The paper states that fully explored states can be pruned, but the experiments use limited visit budgets and model sampling to generate actions.
  2. Do the baselines have access to the same historical information and opportunities for reuse? Are tools, verifiers, and computational budgets consistent across methods?
Reviewer_jJurOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a structured reasoning framework based on a shared AND-OR state graph. In contrast to trajectory-centric methods such as Tree of Thoughts and Graph of Thoughts, equivalent intermediate states are merged both within and across problem instances, allowing outgoing actions, proof status, and verified solution fragments to be reused. The framework further introduces Active Shortcut Discovery (ASD), which periodically asks the generator to construct an action connecting an open state to an already solved region of the graph. Candidate proof subgraphs are verified before a solution is accepted. The method is evaluated on WickedGame24, PrefixBooleanExpression, and the Retro-190 retrosynthetic planning benchmark. It reports Macro-F1 scores of 90.6 and 86.1 on the two LLM reasoning tasks, corresponding to absolute improvements of 25.9 and 19.6 percentage points over the strongest reported baselines. On retrosynthesis, it achieves success rates comparable to prior state-of-the-art planners while reporting fewer reaction and molecule nodes. The appendix additionally develops a least-fixed-point interpretation of truth propagation in cyclic AND-OR graphs and analyzes incremental graph maintenance.

Critical strengths
  1. The shared-state formulation is a meaningful and potentially general contribution. Representing reusable Markovian subproblems once in a shared AND-OR graph is well motivated. It directly addresses redundant computation that trajectory-based reasoning methods cannot avoid, particularly when related instances contain overlapping subproblems. The integration of state reuse, bottom-up proof propagation, and proof-relevant verification forms a coherent reasoning framework rather than an isolated prompting heuristic. The treatment of cyclic support through least-fixed-point semantics also improves the technical completeness of the proposal.

  2. The paper provides promising evidence across distinct domains and explicitly evaluates negative instances. The reported improvements on WickedGame24 and PrefixBooleanExpression are large, and the inclusion of unsolvable or malformed instances exposes hallucinated positive solutions that would not be visible on all-solvable benchmarks. The retrosynthesis experiment further suggests that shared-state reasoning may generalize beyond text-based LLM tasks. If the experimental protocol and accounting are clarified, these results would constitute meaningful evidence for the practical value of reusable-state search.

Critical weaknesses

1. The contribution of Active Shortcut Discovery is not adequately isolated.

The full system combines state merging, cross-instance sharing, MCGS, verification, and Active Shortcut Discovery (ASD), but the ablation only varies verification and ASD. There is no comparison with independent graphs, within-instance sharing, or random shortcut selection. Moreover, ASD decreases Macro-F1 without verification (28.3 to 21.9) and provides only modest accuracy gains when verification is enabled, although it can substantially reduce token use. Thus, the results support ASD as an efficiency mechanism, but do not establish that it explains the large accuracy gains over prior methods.

2. The evaluation protocol does not establish fully reliable or comparable effectiveness and efficiency claims.

The paper lists three LLMs but reports only one score per method, without identifying the model used or whether the baselines were reproduced under matched budgets. The proposed method also shares computation across the entire test batch, whereas most baselines appear to solve instances independently. In addition, the paper provides no uncertainty estimates, does not explain how the new unsolvable labels were validated, and does not clearly define token, iteration, or node accounting for shared graphs. These omissions materially affect the reported accuracy and efficiency advantages.

Questions for authors
  1. Can the authors report independent per-instance search, within-instance state merging, cross-instance sharing without ASD, ASD with random shortcut targets, and the complete method? Please also report merge rates, shortcut proposal and acceptance rates, the fraction of final proofs containing a shortcut, and expansions saved by shortcuts.

  2. Which model produced each Table 1 result? Were the baselines reproduced by the authors or copied from prior publications? If reproduced, did all methods use the same model, prompts, evaluator, verifier access, sampling budget, and stopping rule?

  3. How does the method perform under per-instance cold-start inference, sequential online reuse, and shared batches of different sizes? Is the graph reset between repetitions and between model runs?

  4. Can the authors report uncertainty across repetitions and explain how the solvable/unsolvable labels of WickedGame24 were generated and independently verified? In particular, was the complete symbolic action space exhaustively enumerated?

  5. What exact condition causes FINALIZE to classify a root as unsolvable? Does this represent formal exhaustion of a complete action space or merely failure to find a solution within the visit budget?

  6. Can the authors provide a complete table containing prompt tokens, completion tokens, model calls, verification calls, wall-clock time, and peak graph memory for all methods? How are shared reaction nodes, molecule nodes, and iterations assigned to individual retrosynthesis targets when producing Table 4?

  7. How does the proposed search compare with an exact DP or symbolic graph-search implementation using the same state representation on Game24 and PrefixBooleanExpression? This would help determine whether the remaining errors arise from the search framework or from foundation-model action generation.

Reviewer_wEVDOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes a reasoning framework that uses a shared AND-OR graph to reuse intermediate reasoning states across multiple problem instances. Instead of repeatedly exploring the same states, the framework merges equivalent states and introduces Active Shortcut Discovery to connect unsolved states to previously solved states. Experiments on WickedGame24, PrefixBooleanExpression, and retrosynthetic planning demonstrate improvements.

Critical strengths

1- The paper addresses an important problem in LLM-based search by sharing intermediate states across reasoning trajectories and problem instances.

Critical weaknesses

1- Limited novelty. state merging, AND-OR graphs, and reuse of previously explored states are established concepts in classical AI search and planning. 2- The two LLM reasoning benchmarks involve structured symbolic problems with relatively straightforward state representations. It remains unclear whether the proposed framework would achieve similar benefits on more complex domains such as mathematical reasoning, code generation, or long-horizon planning,

Questions for authors

Why is Macro-F1 selected as the primary evaluation metric for the LLM reasoning tasks?The paper proposes a reasoning framework that uses a shared AND-OR graph to reuse intermediate reasoning states across multiple problem instances. Instead of repeatedly exploring the same states, the framework merges equivalent states and introduces Active Shortcut Discovery to connect unsolved states to previously solved states.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.