Decoding Tree Sketching: A Training-Free Parallel Inference Framework for Large Models

Decoding Tree Sketching (DTS) is a plug-and-play parallel inference framework that can be applied to any large language model (LLM) without training. Using the decoding tree sketching technique, it decomposes complex reasoning tasks into multiple paths that can be explored in parallel, significantly improving inference efficiency and answer quality while maintaining model agnosticism.

Large language models have strong reasoning capabilities, but multi-step token generation leads to latency and computational overhead, which become bottlenecks in practical applications. Traditional optimization approaches such as model compression (quantization, pruning, distillation) and speculative sampling do not change the basic paradigm of single-path sequence generation. DTS proposes a new idea of parallel exploration of multiple paths, similar to how humans try multiple possibilities on scratch paper before choosing the optimal solution.

DTS models the reasoning process as a decoding tree: the root node is the initial problem, intermediate nodes are intermediate reasoning states, leaf nodes are candidate answers, and edges are state transitions. Traditional autoregressive generation uses depth-first single-path exploration, while DTS adopts breadth-first parallel exploration. Its advantages include: time efficiency (reducing waste from suboptimal paths), quality assurance (selecting the optimal path), and diversity (exploring different problem-solving ideas).

The training-free nature of DTS comes from three points: 1. Model-agnostic interface (only uses standard generation interfaces like generate and does not rely on internal states); 2. Prompt engineering-driven (guides the model to generate structured candidate lists through specific templates); 3. External evaluator (uses an independent mechanism to evaluate candidates without relying on the model's own confidence). It can be quickly integrated into existing applications without training data or modifying model parameters.

1. Candidate generation: Guide the model to generate multiple next-step ideas (e.g., 3 different ideas) through prompt templates; 2. Parallel batch processing: Use batch processing support from engines like vLLM and TensorRT-LLM to handle multiple sequences in a single forward pass; 3. Heuristic pruning: Control computational overhead through width limits, depth limits, quality thresholds, and early termination; 4. Path selection: Adopt strategies such as best-first, majority voting, and ensemble learning to select the final answer.

Application scenarios: Mathematical reasoning (parallel exploration of problem-solving paths to select the correct answer), logical reasoning (discovering hidden logical relationships), creative generation (enriching candidates), code generation (selecting the optimal solution from multiple implementation schemes). Experiments show that DTS reduces inference time by 30-50% while maintaining similar or better quality. Comparison: CoT (single path vs parallel), ToT (task-specific vs general), MCTS (complex vs lightweight), self-consistency (no intermediate steps vs process pruning).

Limitations: Memory overhead (parallel candidates require more memory), task applicability (suitable for reasoning tasks with clear intermediate states; less advantageous for pure generation tasks), prompt sensitivity (depends on prompt quality), evaluation quality (simple heuristics may be inaccurate). Recommendations: Start testing with small-scale parallelism, optimize task-specific prompts, adjust strategies based on model characteristics, and monitor search tree states and decision processes.

Insights: LLM reasoning is shifting from single-path to multi-path, and from sequential to parallel, reflecting the parallel exploration strategy that humans use to solve problems; training-free methods have significant value, as they can improve performance without modifying the model. Conclusion: DTS is a lightweight, general-purpose, and efficient parallel framework that is plug-and-play, bringing immediate benefits to LLM applications and will play an important role in practical deployments.