ICML 2025

LLMs Can Reason Faster Only If We Let Them

Bilgehan Sel, Lifu Huang, Naren Ramakrishnan, Ruoxi Jia, Ming Jin

Three side-by-side reasoning diagrams, each running from an Input node at the top to an Output node at the bottom. Left, labelled CoT: a single straight chain of two thought steps. Middle, labelled AoT: a grid of roughly fifteen thought steps with arrows crossing between rows, only three of them marked green as promising while the rest are red dead ends. Right, labelled AoT-O3: a similar grid but with a short path of three green steps and far fewer red steps visited, reaching the output in fewer moves while still branching and backtracking. — **Figure.** Chain-of-Thought reasons in one straight line, Algorithm-of-Thoughts explores widely before committing, and AoT-O3 keeps the exploration but visits far fewer steps on the way to an answer.

Language models handle planning problems better when they are shown reasoning that explores, backtracks, and abandons dead ends, rather than a single straight line of steps. Algorithm-of-Thoughts (AoT) does this inside one query by putting a whole search trajectory in the context, which avoids the repeated API calls that tree-search methods need. The cost is length: AoT answers run many times longer than chain-of-thought answers, which burns context window and tokens. Part of that length appears to be genuine exploration and part of it is stylistic imitation of the demonstrations, and the two are hard to separate. Measurements here on the Game of 24 make the tension concrete: feeding GPT-4 demonstrations centred on 10, 30, and 60 steps produced accuracies of 15%, 31%, and 61%, so simply truncating the reasoning is not a free win.

AoT-O3 separates the two by making length something the model is rewarded for rather than something it copies. Supervised fine-tuning first teaches the format — each step is a state, an explicit thinking/transition step, and a next state, so any earlier state can be resumed and backtracking is expressible. The training trajectories are random-but-valid exploration paths stitched onto segments of correct solutions, not human-authored intuitions. Reinforcement learning (RLOO) then optimises a hand-written scoring function rather than a learned reward model: a correct solution scores max(1 - n*alpha, beta) where n is the number of steps, an incorrect one scores -1, and an optional term adds a bonus to transitions that lie on the correct path. Because there is no reward model to train, the RL stage is cheaper and its feedback is interpretable. The paper is careful to call these per-transition scores value estimates rather than rewards: since every transition is treated as an action, a model that could accumulate a score per step would be pushed to prolong its answer to collect more of them — exactly the padding the method is trying to remove. Notably, random demonstrations that work fine as prompts do not survive fine-tuning — on Game of 24 with Llama-3.3-70B, AoT prompting with random examples reaches 64% while fine-tuning on them collapses to 5%.

Across Game of X, N-Puzzle, and Word Ladder, on Gemma2-2B, Llama3-1B, and Llama3-3B, shorter solutions came with higher accuracy rather than a trade-off. On Game of X the paper reports length reductions of 51.3% to 62.4% alongside accuracy gains of 11-17 percentage points; the most notable single change is Llama3-1B going from 31.9 steps at 55% accuracy to 9.7 steps at 72%. N-Puzzle reductions run 27.8% to 46.0%, and on Word Ladder, Llama3-1B drops 47.1% in length (26.1 to 13.8 steps) while accuracy rises from 47% to 52%.

Key results

Solution length is not free padding: GPT-4 prompted with demonstrations averaging 10, 30, and 60 steps on Game of 24 reached 15%, 31%, and 61% accuracy respectively.
The RL stage replaces a learned reward model with a hand-written step-count score — max(1 - n*alpha, beta) for correct solutions, -1 for incorrect — so nothing has to be trained to supply the signal. Because each transition counts as an action, the paper treats those per-step scores as value estimates rather than summable rewards, which is what keeps the model from prolonging its answer to collect more of them.
Random search trajectories work as prompts but not as fine-tuning data: on Game of 24 with Llama-3.3-70B, AoT scores 64% when prompted with random examples and 5% when fine-tuned on them.
Shorter and more accurate at once: Llama3-1B on Game of X goes from 31.9 steps at 55% accuracy (AoT-SFT) to 9.7 steps at 72%; the paper's headline claim is a reduction of up to 80% versus baseline AoT.

BibTeX

@inproceedings{sel2025llms,
  title     = {{LLM}s Can Reason Faster Only If We Let Them},
  author    = {Sel, Bilgehan and Huang, Lifu and Ramakrishnan, Naren and Jia, Ruoxi and Jin, Ming},
  booktitle = {Proceedings of the 42nd International Conference on Machine Learning},
  series    = {Proceedings of Machine Learning Research},
  volume    = {267},
  year      = {2025},
  publisher = {PMLR},
  address   = {Vancouver, Canada}
}