Active Shortcut Discovery in Shared State Graphs for Foundation Model Reasoning

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.