acceptodds
Under review as a conference paper at ICLR 2027

Gradient Descent on Tokens Is Sparse: Understanding the Computational Structure of Differentiable Token Optimization

Abstract

Inference-time computation has become an important factor in language model quality, and differentiable token optimization (DTO) is one way to allocate this computation. DTO treats a model's discrete output tokens as continuous parameters and refines them using gradient descent. Test-time reasoning, adversarial attacks and controllable generation all share this template, and every member's default gives each position the same fixed budget at every step, presuming that the computation is homogeneous. This assumption does not hold, because DTO is a discrete process evaluated through a continuous surrogate, and the two decouple within the first few dozen updates. Once a position's margin exceeds what a single step can overturn, the surrogate's gradients can no longer alter the discrete output. The resulting computation is not merely redundant, since updates to uncommitted positions can continue to alter the output without improving quality. Accuracy falls monotonically from 47.1% at greedy decoding to 34.2% at T=60, with losses outnumbering gains 32 to 1. Because the decoupling arises from the interface between continuous optimization and discrete token assignment rather than from any particular objective, it holds across the family and is measurable. Tracking 340 discrete trajectories over two model families on MATH-500, we find at least 89% of token flips within the first 50 of 59 measurements, the most active fifth of positions absorbing a third of the churn, and a churn plateau that never converts into quality. Three propositions characterize what can be recovered from the decoupling and yield three mechanisms, gradient reuse across stable updates, position-level activity prediction, and objective-driven stopping with a loss bound. Acting on the structure jointly removes 15.8% of model calls at T=60 without measurable loss of accuracy. The budget of DTO is therefore a measurable property of the decoupling rather than a constant to be tuned.

Primary area:
optimization
Keywords:
Test-time compute, LLM reasoning, efficient inference, discrete optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_XHS3OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the computational behavior of differentiable token optimization. The authors find that token changes are concentrated in a small number of positions and early optimization steps, while longer optimization often hurts answer quality. Based on these observations, they explore gradient reuse, position-level activity prediction, and early stopping. Experiments on MATH-500 and GSM8K reveal similar patterns, with 15.8% fewer model calls at comparable accuracy on a 40-problem MATH-500 subset.

Critical strengths
  1. The paper offers an interesting analysis of token-level optimization dynamics, showing that computation is unevenly distributed across positions and optimization steps.
  2. The empirical findings could be useful, particularly the observation that additional gradient updates can reduce accuracy rather than improve it.
  3. The paper connects its observations to practical optimization strategies and provides ablations to measure their individual contributions.
Critical weaknesses
  1. The experiments are limited to a single reward-model-based objective with fixed hyperparameters. The paper does not test whether its findings hold under other optimization settings or DTO methods. In particular, the original ∇-Reasoner configuration and other DTO methods such as GCG are not evaluated.
  2. The practical benefit of the proposed acceleration is unclear. The optimized outputs perform worse than greedy decoding, and the proposed method saves only 15.8% of model calls. Simply using fewer optimization steps could achieve much larger savings with better accuracy, raising questions about the need for the proposed mechanisms.
  3. The efficiency evaluation is limited. Savings are measured in model calls rather than wall-clock time, and the joint evaluation covers only 40 problems. Most savings come from gradient reuse, while the other two components contribute relatively little.
  4. The theoretical analysis is not well connected to the experiments. Some results rely on assumptions that are not verified, and the experiments use a different optimizer from the one analyzed. Moreover, the stopping rule covered by Proposition 3 is not evaluated.
Questions for authors
  1. Would the findings still hold with different hyperparameters or DTO methods, especially the original ∇-Reasoner setup and GCG? It would be helpful to see results under these settings.
  2. Could the authors directly compare the proposed approach with a shorter fixed optimization budget in terms of accuracy and compute? This would help clarify when the proposed mechanisms are actually beneficial.
  3. Could the authors report actual wall-clock speedups and test the method on more problems?
  4. How well do the theoretical assumptions hold in practice? Also, why wasn't the stopping rule in Proposition 3 tested?
  5. Could the authors run larger no-cache experiments to check whether stale gradients affect the results?
Reviewer_DHL2OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper introduces theoretical and empirical analysis of differentiable token optimization (DTO). This is the family of methods in which the final discrete tokens are calibrated and updated based on the updates of the logits with gradient descent to maximize an objective, for example a reward model score. The paper does not propose a new DTO method. Instead, it analyzes where the computation of the standard DTO procedure goes, by recording the discrete tokens after every update. The authors find that most token flips happen in the first few dozen steps, mainly at positions where the model is uncertain, while most positions almost never change. After this early phase, a small set of positions (something like 1%) keeps flipping back and forth, and accuracy goes down. Based on these observations, the authors propose three mechanisms (gradient reuse, freezing positions that are unlikely to change, and early stopping), which together reduce the number of model calls by 15.8% without a measurable loss of accuracy.

Critical strengths

Strengths

  1. A detailed analysis of the token-level dynamics of DTO, a relatively new family of test-time methods. Recording the discrete tokens after every step shows effects that the continuous loss hides.
  2. The main observations are repeated on two model families (Qwen2.5-7B and Llama-3.1-8B) on MATH-500, and on GSM8K for Qwen. The results are consistent across these settings.
  3. The analysis gives a clear intuition: uncertain positions change, while confident positions stay fixed. Entropy measured before the optimization predicts which positions will flip (AUC 0.81).
  4. The proposed mechanisms are simple and reduce the number of model calls by 15.8% without a measurable loss of accuracy, although this is shown only on 40 problems with very low absolute accuracy (2-3 out of 40).
Critical weaknesses
  1. In this setting, DTO does not improve over greedy decoding: greedy is better than every optimization budget on MATH-500, and even the reward-model score goes down (-1.79 for Qwen, -3.57 for Llama). So it is unclear why one would run DTO, or why it matters to make it cheaper. This contradicts the original ∇-Reasoner paper (Wang et al., 2026), which reports clear gains on the same models (e.g., 71.2% to 80.4% on MATH-500 for Qwen2.5-7B-Instruct). The setup here differs a lot (100x larger learning rate, no gating or acceptance step, a weaker prior, shorter generations), so the negative results may come from this configuration rather than from DTO itself.
  2. The propositions are derived for plain gradient descent, but all experiments use Adam with a large learning rate (1.0). Adam normalizes the step size for each coordinate, so the flip condition and the role of the gradient norm may be different in the measured regime. In general, the theory is quite light: Proposition 1 is close to the definition of an argmax change, and Proposition 2 relies on an isotropy assumption.
  3. DTO is not compared with sampling-based test-time methods, such as Best-of-N with the same reward model, self-consistency or beam search, at the same compute. In the paper's own cost metric, a DTO run costs 4T model calls and Best-of-N about 2N, so Best-of-N with N ≈ 2T is a fair comparison. Even Best-of-8 or Best-of-16 would be much cheaper than DTO with T = 60, and the original ∇-Reasoner paper itself compares against Best-of-8 and self-consistency.
  4. The experimental setup is limited: 4-bit quantized 7-8B models, generation limited to 128 or 512 tokens, and a single seed. The greedy accuracy of Qwen2.5-7B-Instruct (47.1%) is much lower than what is usually reported for this model (e.g., 71.2% on MATH-500 in the ∇-Reasoner paper).
  5. The paper claims that the findings hold for the whole DTO family, but all measurements use only one instance (∇-Reasoner-style optimization in logit space); GCG is described but not tested.
Questions for authors
  1. How does DTO compare with Best-of-N (using the same reward model) at the same number of model calls or beam search?
  2. Do the accuracy decline and the flip dynamics still hold with the ∇-Reasoner configuration (β = 1, with gating and acceptance), or with a smaller learning rate?
  3. What fraction of the greedy outputs reaches the 512-token limit or contains repetition loops that were improved with DTO?
  4. Why did you modify original ∇-Reasoner parameters?
4 comments

Dear Reviewer,

With the author response deadline approaching, we wanted to ask whether you have any remaining questions or concerns. We’d be happy to clarify any points while the discussion is still open.

If our responses have addressed your concerns, we would appreciate it if you could let us know whether you would consider raising your score.

Thank you again for your time and thoughtful feedback.

Best regards,

The Authors

Thank you for the additional experiments. The step-size and prior-weight comparisons addressed my question about the accuracy decline. However, I also share Reviewer fJA3's concern about whether the full accelerated loop preserves accuracy when the reference loop performs better. A direct comparison at the smaller step size or with the stronger prior would help answer that question. I'm keeping my score.

AuthorsOpenReview ↗

The accelerated loop preserves the reference's greedy accuracy at both settings, and its measured time saving is largest there

Yes, at both settings the comment names, from the recorded runs rather than from a new one. The loop has three components, the reuse cache, the stopping rule of Section 4.3.3 and shared position selection. The cache is inside the reference runs at each setting, the stopping rule is applied offline to the traces those runs recorded, and position selection is bounded by the edits it could withhold. At beta = 1.0 the loop returns 22 of 24, the reference's full-budget count, and at eta = 0.1 it returns 22 of 24 against the reference's 23, which is every answer the reference holds at greedy decoding.

Those settings are where the reference performs better. At beta = 1.0 it holds 22 of 24 at greedy decoding and at every checkpoint to T = 60, against 7 of 24 at T = 60 under the default, and all 24 problems keep their status across the checkpoints (Appendix G, p26). At eta = 0.1 it holds 22 at greedy decoding, 23 at T = 5, T = 10 and T = 60 and 22 at T = 20 and T = 40, the only problems that vary being index 177, right at T = 60 alone, and index 184, right at T = 5 and T = 10 alone. The 2 of 60 in the earlier comment is the 128-token cap truncating a correct derivation before its boxed answer (Appendix C.2, p19), and the same 60 problems give 22 of 60 at greedy decoding under the 512-token cap that sets these levels.

The cache serves 74.5% of steps at beta = 1.0 and 39.6% at eta = 0.1, against 3.6% at the default, so most of the acceleration is already inside the run whose accuracy the paragraph above reports. The stopping rule halts 23 of the 24 at beta = 1.0, median step 12, saving 42.3 of the 60 steps, and since every problem's status is constant there, each halt lands on the full-budget answer. At eta = 0.1 it halts 13 of the 24, median step 26, saving 18.9, and the halted answers give 22 of 24, the one answer it leaves behind being index 177, which halts at step 40 while its correct answer appears only on the final update. Position selection acts only by withholding an edit, and the reference makes 19.6 flips per problem at beta = 1.0 and 67.3 at eta = 0.1, against 236.2 at the default. Where the full loop has been run end to end, at the default over the 100 problems, none is lost and one is gained, the decoded answer is identical on 56 of the 60, the four differences are wrong under both loops (exact McNemar p = 1.0, one-sided Clopper-Pearson 95% bound 4.9%), and the joint loop is faster on 57 of the 60, with per-problem wall-clock 0.882 of the reference's, bootstrap [0.854, 0.908], median 0.910 (Section 4.4, Appendix F.1).

The reference takes 30.6 minutes per problem at beta = 1.0 and 51.5 at eta = 0.1, against 98.2 at the default, reductions of 68.9% and 47.5% where the paired default run, with both the cache and the rule at their least room, saves 11.8%. The answer is therefore yes at both settings, with accuracy held and the largest measured time saving exactly where the reference is strongest.

Thank you for clarifying and the analysis of the saved runs. My question was about a direct comparison of accuracy and runtime between the full accelerated loop and the reference loop at the smaller step size or with the stronger prior. This still remains open for me, so I'm keeping my score.

Reviewer_fJA3OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary
  • The paper studies when and where tokens change during differentiable token optimization, and how continued optimization affects answer quality.
  • It combines gradient reuse, position prediction and stopping, reporting 15.8% fewer model passes on a 40-problem evaluation.
Critical strengths
  • Up and coming area, a structured overview paper like this one can be very valuable
  • Recording discrete token trajectories gives a useful view of computation that final accuracy alone misses; the qualitative patterns are examined across two model families and two tasks.
  • The paper implements and ablates mechanisms for using these observations, rather than stopping at descriptive analysis.
Critical weaknesses
  • The accuracy decline is established under a specific setup (Adam learning rate 1.0 and prior weight β=0.001). Without comparisons using smaller/annealed steps and the reference β=1, it is unclear how much reflects the proposed structural explanation versus lack of tuning lr + scheduler + other hyperparams
  • The joint efficiency evaluation covers only 40 problems, with 3 correct answers versus 2 for the reference. This is insufficient to establish reliable accuracy preservation, and fewer model passes do not establish wall-clock savings. These limits motivate my weak-rejection recommendation.
  • Not clear what the main insights are, authors can bold this in the introduction, right now feels more like a workshop paper
Questions for authors
  • Does accuracy decline persist with annealed learning rates and the reference prior weight β=1? Possibly overshooting the optima?
  • Can the authors just show what tokens it comes up with? Curious if it resembles prompt-engineered sentences or truly are noisy
  • Can we use adverserial attack methods such as gradient-guided discrete search (Zou et al., 2023, https://arxiv.org/abs/2307.15043) as these have been well-studied for years? How do they fare as token-optimization baselines?
  • Can the authors try Natural Evolutionary Strategies or non-backprop-based gradient estimators to avoid bias from STE?
1 comment

Thanks for adding these!

As both loops got 2/60 problems right on that set, I’m unsure whether the joint loop preserves accuracy when the reference performs better.

If you already have results with the smaller step size or stronger prior, could you share the paired accuracy and wall-clock time for the joint and reference loops under the same setting?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.