TTA*: A New Paradigm for Small Model Reasoning, Test-Time A* Search Algorithm Without Fine-Tuning

TTA* (Test-Time A* Search) is a new reasoning enhancement method for small language models. Its core lies in transforming multi-step reasoning into goal-oriented tree search, guiding the model to self-improve during reasoning via the cost function of the A* algorithm. This method enhances the complex reasoning capabilities of small models without fine-tuning or external reward models, providing a new idea for model optimization in resource-constrained scenarios.

Large language models (such as GPT-4, Claude) have strong reasoning capabilities but high deployment costs; small models are resource-friendly but perform poorly in complex reasoning tasks. Traditional solutions to improve small model reasoning capabilities rely on expensive fine-tuning or complex reinforcement learning training, which have high thresholds. TTA* shifts the optimization focus from the training phase to the reasoning phase, enabling capability improvement without changing model weights.

TTA* is based on the A* search framework, with the core cost function f(n)=w·depth(n)+(100-Reward(n)):

• Path cost g(n): Penalizes lengthy reasoning and encourages concise solutions;
• Heuristic evaluation h(n): Calculated via the median reward value of the model's self-evaluation to reduce evaluation noise. Search process: Select the node with the smallest f value, generate improved candidates through self-criticism, and add them to the search frontier after evaluation. The self-criticism mechanism uses the median of multiple evaluations and generates specific critical text to guide improvement.

TTA* was validated on the GSM8K mathematical reasoning dataset (about 8000 primary school math problems). Experimental configurations can be flexibly controlled via parameters (e.g., max_iter controls the number of iterations, num_children controls the number of child nodes). The code adopts a modular design:

• Core modules: LLMWrapper (model calling), Node (node logic), TTAStar (search main loop), evaluate.py (accuracy calculation);
• Experimental script: run_gsm8k.py integrates the process and supports command-line parameter configuration.

Advantages:

1. Training-agnostic: No need for fine-tuning or RL training;
2. Model-agnostic: Applicable to any language model with basic generation capabilities;
3. Interpretability: Transparent search process, allowing tracking of improvement paths;
4. Resource-friendly: Can run on small models. Limitations:
5. Increased reasoning cost: Requires multiple generations and evaluations;
6. Parameter tuning: Needs to adjust search parameters according to tasks;
7. Task applicability: Simple tasks may not be worth the effort.

The TTA* team plans to support more challenging mathematical reasoning datasets (such as MATH500, MATH401, AIME) to further verify effectiveness in complex scenarios. In addition, this method can be extended to other fields:

• Code generation: Gradually improve candidate code;
• Logical reasoning: Apply to multi-step logical deduction tasks;
• Creative writing: Iteratively generate high-quality text.

TTA* represents a paradigm shift in reasoning optimization—from training resource investment to reasoning algorithm optimization, echoing the successful ideas of models like DeepSeek-R1. For enterprises, it can improve performance by increasing reasoning computation investment without retraining models, offering high flexibility. The TTA* code has been open-sourced; interested parties can visit the GitHub repository to obtain implementations and experimental scripts.