AStar: Boosting Multimodal Reasoning with Automated Structured Thinking
AStar uses retrieved thought cards to boost training-free multimodal reasoning, reaching 53.9% on MathVerse.
Key Findings
Methodology
AStar is a training-free Automatic Structured Thinking framework. Using 500 seed samples, it runs Monte Carlo Tree Search (MCTS) to obtain reasoning trajectories, then distills them into thought cards. Cards encode six vision-language actions: Visual Parsing, System Analysis, One-Step Thought, Chain-of-Thought, Divide and Conquer, and Self-Reflection. At test time, five cards are retrieved using problem complexity (PC) and text-image semantics (TIS); candidate solutions are generated and verified through self-consistency and text-domain outcome rewards.
Key Results
- With Qwen2.5-7B, AStar reaches 53.9% on MathVerse, exceeding GPT-4o at 50.2%, URSA-8B at 45.7%, and R1-VL-7B at 40.0%. On MathVision it reaches 32.7%, above GPT-4o’s 30.4%.
- The strategy transfers beyond mathematics. AStar raises GPT-4o from 70.3% to 73.2% on MMMU and from 47.8% to 52.2% on GAOKAO-MM; Qwen2-VL-2B rises from 35.3% to 44.3% on GAOKAO-MM.
- AStar requires only 0.5K prior samples and 50 minutes of preprocessing, with no parameter updates. Its data requirement is 520 times lower than Mulberry’s 260K and 2,200 times lower than URSA-8B’s 1,100K.
Significance
AStar addresses three persistent bottlenecks in multimodal reasoning: the high cost of explicit search, the data and compute demands of supervised post-training, and the instability or shallow exploration of reinforcement learning. It shows that high-level reasoning strategies can be stored externally and invoked at inference time rather than permanently encoded in model parameters. Academically, this offers a useful framework for studying interactions between implicit model competence and explicit procedural guidance. Industrially, it is attractive for private, resource-constrained systems that need rapid adaptation to new visual reasoning tasks.
Technical Contribution
The framework combines MCTS and UCT for discovering useful trajectories, a Value-of-Computation-inspired score Score=kR-(1-k)C for balancing reward and action cost, PC and CLIP-based TIS for lightweight card indexing, rank fusion for selecting five cards, and self-consistency plus outcome rewards for verification. Unlike per-problem MCTS, it amortizes search into a reusable strategy repository. Unlike SFT, PPO, or GRPO, it changes neither model parameters nor the training distribution and can be composed with post-trained models.
Novelty
The novelty lies in converting a small set of searched reasoning traces into reusable, problem-conditioned action templates. MCTS, Chain-of-Thought, and retrieval are not individually new; the contribution is their integration as an external procedural memory. Most related methods either explore each problem explicitly or learn strategies implicitly through large-scale post-training. AStar occupies a lightweight middle ground: discover strategies offline, retrieve them adaptively, and instantiate them at test time.
Limitations
- Performance depends on seed quality and MCTS preprocessing. If a novel task has no semantically or structurally related card, nearest-neighbor retrieval may provide misleading guidance rather than useful decomposition.
- Reliable visual-domain verifiers are unavailable, so AStar uses self-consistency and text-domain reward models. These may fail to detect image-reading, geometry, chart-localization, or diagram-grounding errors.
- Generating five candidate trajectories increases test-time latency, while card abstraction and performance depend on choices such as k, action depth, and retrieval design.
Future Work
Future work should develop visual process and outcome verifiers, learn finer-grained card representations, and dynamically allocate the number of cards and reasoning steps. Evaluation should expand to multilingual, video, embodied, and real-world-agent tasks. Combining AStar with SFT, PPO, and GRPO may yield systems in which parametric reasoning skills and an editable external strategy library complement each other while reducing inference cost.
AI Executive Summary
Multimodal large language models can recognize images and answer routine questions, yet they remain unreliable on geometric diagrams, charts, and multistep visual mathematics. Existing solutions either search many possible reasoning paths with Beam Search or MCTS, incurring heavy computation, or use SFT, PPO, or GRPO to train long-chain reasoning, demanding large datasets and potentially unstable optimization. AStar proposes a third route: structured guidance at inference time without changing model parameters.
Its central device is the thought card. From 500 seed examples, MCTS uses UCT to explore actions, simulate completions, and backpropagate rewards. A Value-of-Computation-inspired score, Score=kR-(1-k)C, selects paths that balance correctness and length. These paths are distilled into templates composed of six actions, such as Visual Parsing, System Analysis, Chain-of-Thought, Divide and Conquer, and Self-Reflection. For a new query, PC and CLIP-based TIS retrieve five relevant cards; the model instantiates them and verifies candidate answers.
The results are substantial. Qwen2.5-7B with AStar scores 53.9% on MathVerse versus GPT-4o’s 50.2%, and 32.7% on MathVision versus 30.4%. It achieves 62.3% on MMStar, exceeding Mulberry’s 61.3%, using only 0.5K samples and 50 minutes of preprocessing. Cards also transfer to MMMU and GAOKAO-MM. Remaining concerns include visual verification, retrieval failures under distribution shift, and the latency of five candidates. AStar therefore reframes reasoning improvement as reusable strategy memory rather than repeated search or costly retraining.
Deep Analysis
Background
MLLMs evolved from LLaVA and InternVL to Qwen2-VL, while OpenAI-o1 and DeepSeek-R1 renewed interest in System-2-style long Chain-of-Thought. Mulberry explores solutions explicitly; URSA, R1-VL, LMM-R1, and MM-Eureka use SFT or RL. These methods improve reasoning but require substantial search, data, compute, or stable rewards.
Core Problem
A base MLLM often defaults to direct prediction and does not reliably decide when to parse an image, decompose a task, expand a chain, or reflect. Per-query search repeatedly explores similar strategy spaces; post-training hides strategies inside parameters, requires costly data synthesis, and may narrow exploration.
Innovation
AStar externalizes reasoning strategy as thought cards rather than complete answers. Each card stores an abstract action template plus PC and TIS statistics. MCTS discovers strategies from few examples; VOC-style scoring compresses them; adaptive matching selects cards for each query; verification filters candidate outputs. This amortizes search while preserving model flexibility.
Methodology
- �� Define six actions: VP, SA, OST, CoT, DC, and SR.
- �� Run MCTS on seed questions; UCT(s)=Q(s)+w√(lnN(p)/N(s)) balances exploration and exploitation.
- �� Use terminal self-consistency as reward and propagate Q(p)←(1-α)Q(p)+αQ(s).
- �� Select paths with Score=kR-(1-k)C and distill them into cards.
- �� Represent text-image semantics as TIS=(EI(i)+ET(t))/2, alongside PC.
- �� Retrieve the five best cards, instantiate five solutions, and verify them with self-consistency and text-domain outcome rewards.
Experiments
Experiments cover MathVista, MathVerse, MathVision, MMMU, GAOKAO-MM, ChartQA, MMStar, and BLINK. Backbones include Qwen2.5-7B and Qwen2-VL-2B/7B. Baselines include Qwen2-VL, InternVL, Math-LLaVA, URSA, R1-VL, LMM-R1, MM-Eureka, Mulberry, and GPT-4o. Ablations remove cards, replace matching with random cards, or replace verification with random selection or self-consistency.
Results
AStar reaches 53.9% on MathVerse, including 64.4% on vision-dominant cases and 59.5% on logical reasoning; MathVision reaches 32.7%. MMStar reaches 62.3% versus Mulberry’s 61.3%. Removing thought cards lowers average MathVision/MathVerse performance from 43.3% to 33.8%; removing matching lowers it to 37.6%. Increasing seeds from 50 to 500 raises the average from 33.5% to 43.3%.
Applications
The method fits educational mathematics, chart question answering, scientific visual QA, document analysis, and local small-model deployment. A user needs an image-capable MLLM, a modest representative seed set, and offline card construction; no parameter training is required. This supports privacy-sensitive applications and rapid adaptation to changing task distributions.
Limitations & Outlook
AStar still incurs offline MCTS cost and five-way test-time generation. PC and CLIP similarity may not capture fine geometric relations, while text-domain rewards are imperfect substitutes for visual verification. Future systems should add visual process rewards, dynamic computation budgets, editable cards, and evaluations on multilingual, video, embodied, and real-world interactive tasks.
Plain Language Accessible to non-experts
Imagine a kitchen receiving complicated orders. A conventional model is a cook who glances at the ticket and immediately serves a dish: fine for simple meals, risky for elaborate ones. Search-based methods ask the cook to try every possible recipe from scratch, which is slow. Post-training sends the entire kitchen through an expensive retraining program.
AStar instead studies 500 previous orders and writes reusable recipe cards: inspect the ingredients, break the dish into parts, cook each part, and taste everything again. When a new order arrives, it chooses five cards whose difficulty and ingredients resemble the order. The cook then prepares several versions and keeps the answer that is most consistent and best verified.
The cards do not contain the final dish; they contain a useful route to the dish. With only 50 minutes of preparation, Qwen2.5-7B reaches 53.9% on MathVerse, beating GPT-4o’s 50.2%. The trade-off is that poor cards or weak checking can still lead to mistakes, and trying five versions takes extra time.
ELI14 Explained like you're 14
Think of an AI solving a tricky game puzzle. A basic AI sees a locked door and immediately guesses the code. That works on easy levels, but not when the puzzle has pictures, several steps, and traps. One solution is to try every possible move, but a huge game map makes that painfully slow. Another is to train the AI for ages with tons of examples.
AStar gives it a deck of strategy cards instead. The researchers let the AI study 500 old problems and record patterns such as “look carefully at the picture,” “split the big task,” “reason step by step,” and “check your answer.” For a new puzzle, it picks five cards that seem to match the difficulty and image. It tries those routes and compares the results.
No new brain surgery is needed: the model’s parameters stay unchanged. Qwen2.5-7B plus AStar scores 53.9% on MathVerse, higher than GPT-4o’s 50.2%, and reaches 32.7% on MathVision. The same math strategies even help science and chart questions!
Is it perfect? Nope! If the card collection lacks a useful strategy, or if the AI misunderstands the image, it can still fail. Checking five routes also takes extra time. Better visual judges and smarter time budgets are the obvious next upgrades.
Glossary
Thought Card
A reusable high-level reasoning template rather than a stored answer. Technically, it couples an action sequence with complexity and multimodal semantic statistics.
AStar builds cards offline and retrieves them during inference.
Monte Carlo Tree Search (MCTS)
A tree-search procedure that repeatedly selects, expands, simulates, and backpropagates candidate decisions. It estimates which reasoning actions are promising.
Used to generate trajectories from 500 seed problems.
Upper Confidence Bounds applied to Trees (UCT)
A node-selection rule balancing exploitation of high-value states and exploration of under-visited states. The paper uses Q(s)+w√(lnN(p)/N(s)).
It controls MCTS selection during card construction.
Problem Complexity (PC)
A lightweight estimate of task difficulty derived from the image-text input. It allows cards to be matched by reasoning demand, not only topic.
PC is combined with TIS for retrieval.
Text-Image Semantics (TIS)
A joint representation of image and text semantics, computed as the average of CLIP image and text encodings. It measures multimodal similarity.
TIS ranks cards against a test query.
Value of Computation
A metareasoning principle that weighs expected benefit against computational cost. AStar implements it as Score=kR-(1-k)C.
It selects concise yet reliable trajectories.
Open Questions Unanswered questions from this research
- 1 Visual verification remains unresolved: self-consistency and text rewards may miss grounding, geometric, or chart-localization errors, motivating visual process and outcome reward models.
- 2 The mechanism of cross-domain transfer is unclear. More controlled studies are needed to identify which action patterns generalize and when semantic mismatch causes harmful retrieval.
- 3 The optimal trade-off between five candidate solutions, accuracy, latency, and compute budget has not been theoretically characterized.
Applications
Immediate Applications
Educational math and chart tutoring
Learning platforms can build cards from a small archive of diagram and chart questions. A 7B-scale model can parse, decompose, solve, and verify without retraining, making deployment practical when curricula and question banks change frequently.
Scientific document question answering
Research organizations can apply cards to figures, apparatus diagrams, and statistical plots. Open-source vision-language models can run the workflow locally, while the reported 50-minute preparation makes private or rapidly updated systems easier to maintain.
Long-term Vision
A composable multimodal reasoning layer
Thought cards could become an editable strategy library for multilingual, video, robotic, and agentic systems. Models would select procedures according to risk and budget, combining parametric knowledge with transparent external reasoning programs.
Abstract
Multimodal large language models excel across diverse domains but struggle with complex visual reasoning tasks. To enhance their reasoning capabilities, current approaches typically rely on explicit search or post-training techniques. However, search-based methods suffer from computational inefficiency due to extensive solution space exploration, while post-training methods demand substantial data, computational resources, and often exhibit training instability. To address these challenges, we propose \textbf{AStar}, a training-free, \textbf{A}utomatic \textbf{S}tructured \textbf{t}hinking paradigm for multimod\textbf{a}l \textbf{r}easoning. Specifically, we introduce novel ``thought cards'', a lightweight library of high-level reasoning patterns abstracted from prior samples. For each test problem, AStar adaptively retrieves the optimal thought cards and seamlessly integrates these external explicit guidelines with the model's internal implicit reasoning capabilities. Compared to previous methods, AStar eliminates computationally expensive explicit search and avoids additional complex post-training processes, enabling a more efficient reasoning approach. Extensive experiments demonstrate that our framework achieves 53.9\% accuracy on MathVerse (surpassing GPT-4o's 50.2\%) and 32.7\% on MathVision (outperforming GPT-4o's 30.4\%). Further analysis reveals the remarkable transferability of our method: thought cards generated from mathematical reasoning can also be applied to other reasoning tasks, even benefiting general visual perception and understanding. AStar serves as a plug-and-play test-time inference method, compatible with other post-training techniques, providing an important complement to existing multimodal reasoning approaches.