Elamur Research⌕
☰
home / papers / 2026 / SD-E2: Semantic Exploration for Reasoning Under Token Budgets

SD-E2: Semantic Exploration for Reasoning Under Token Budgets

Paper · 2026 · Kshitij Mishra, Nils Lukas and Salem Lahlou

Summary

Small language models have a hard time with multi-step reasoning when token budgets are tight. They need to try different solution approaches, but sampling many traces is costly. Standard RL rewards such as GRPO also cannot tell a new strategy apart from a reworded old one. The authors propose SD-E2, an RL framework that rewards exploration only when it is meaningfully new.

A frozen sentence encoder embeds each generated reasoning strategy. Two quantities are rewarded: how many strategies are semantically unique under a similarity threshold, and how dissimilar they are on average. As soon as any strategy reaches the correct answer, the reward changes to a fixed exploitation bonus. The diversity term is combined with correctness, format and efficiency terms, each z-score normalized per batch, and the whole objective is optimized with GRPO and KL regularization.

On GSM8K with Qwen2.5-3B-Instruct, SD-E2 beats the base model and both GRPO baselines. It also helps on AIME and MedMCQA without spending more tokens. The authors see this as a way to strengthen compact models by restructuring the reasoning process rather than adding parameters.

Key points

  • GSM8K (Qwen2.5-3B-Instruct):
    • Accuracy rises from 54.66% to 82.03%, roughly +27 pp over the base model.
    • The gain is about +5.2 pp over GRPO-CFL and +1.5 pp over GRPO-CFEE (80.52%). The paper reports slightly different deltas in different sections.
    • The model finds 9.78 distinct strategies per problem on average, with S-ACC of 97.2%.
  • Llama backbone: the method transfers without retuning, reaching 75.4% on GSM8K.
  • AIME 1983–2025 (963 problems): accuracy is 13.28%, compared with 6.74% for the base model and 9.87% for GRPO-CFEE, at a similar token count (about 710).
  • MedMCQA (val): accuracy is 49.64%, compared with 38.37% for the base model and 48.76% for GRPO-CFEE.
  • Training setup and limitations:
    • Training uses 4-bit QLoRA on 3B models.
    • Results depend on the frozen encoder, which may be unreliable for non-English text.
    • Results are sensitive to the similarity threshold δ.
    • The model can commit too early when two plausible strategies nearly agree.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,426 works

Cite

Cite as Kshitij Mishra, Nils Lukas and Salem Lahlou. 2026. SD-E2: Semantic Exploration for Reasoning Under Token Budgets. Findings of the Association for Computational Linguistics: EACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-eacl.323

@inproceedings{mishra2026sd,
  title = {{SD-E2: Semantic Exploration for Reasoning Under Token Budgets}},
  author = {Kshitij Mishra, Nils Lukas and Salem Lahlou},
  booktitle = {Findings of the Association for Computational Linguistics: EACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-eacl.323},
  url = {https://doi.org/10.18653/v1/2026.findings-eacl.323}
}

References

50 references, 19 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Sergio Aznarez, Jannik Kossen, Ethan Dyer, and 1 others. 2023. Implicit preference optimization: Efficient fine-tuning without preference pairs. arXiv preprint arXiv:2310.08560. find
  2. Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, and 1 others. 2022. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05862. Referred to as Bai e… find
  3. Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, and et al. 2023. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303.12712.
  4. Jaime Carbonell and Jade Goldstein. 1998. The use of mmr, diversity-based reranking for reordering documents and producing summaries. In Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, pages 335–336. for question answering over… find
  5. Siqi Chen and et al. 2023. Phi-2: The surprising power of small language models. arXiv preprint arXiv:2312.16868. — [arXiv:2312.16868](https://arxiv.org/abs/2312.16868) find
  6. Miyoung Ko, Sue Hyun Park, Joonsuk Park, and Minjoon Seo. 2024. Hierarchical deconstruction of LLM reasoning: A graph-based framework for analyzing knowledge utilization. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 4995–5027, Miami, Florida, USA.… find
  7. Yilei Chen, Souradip Chakraborty, Lorenz Wolf, Ioannis Ch Paschalidis, and Aldo Pacchiano. 2025. Enhancing diversity in large language models via determinantal point processes. arXiv preprint arXiv:2509.04784. — [arXiv:2509.04784](https://arxiv.org/abs/2509.04784) find
  8. Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. In Advances in Neural Information Processing Systems, volume 35, pages 22199–22213.
  9. Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. 2017. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30. find
  10. Alex Kulesza, Ben Taskar, and 1 others. 2012. Determinantal point processes for machine learning. Foundations and Trends® in Machine Learning, 5(2–3):123– 286. find
  11. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, and 1 others. 2021. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168.
  12. Salem Lahlou, Abdalgader Abubaker, and Hakim Hacid. 2025. Port: Preference optimization on reasoning traces. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 10989… find
  13. DeepSeek-AI. 2025. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. https://arxiv.org/abs/2501.12948. ArXiv:2501.12948. ↗
  14. William Fedus, Barret Zoph, and Noam Shazeer. 2022. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. Journal of Machine Learning Research, 23(120):1–39. find
  15. Boqing Gong, Wei-Lun Chao, Kristen Grauman, and Fei Sha. 2014. Diverse sequential subset selection for supervised video summarization. Advances in neural information processing systems, 27. find
  16. Alex Graves. 2016. Adaptive computation time for recurrent neural networks. arXiv preprint arXiv:1603.08983. find
  17. Alex Havrilla, Sharath Raparthy, Christoforus Nalmpantis, Jane Dwivedi-Yu, Maksym Zhuravinskyi, Eric Hambro, and Roberta Raileanu. 2024. Glore: When, where, and how to improve llm reasoning via global and local refinements. arXiv preprint arXiv:2402.10963.
  18. Qingxiu Huang, Jun Wang, Lei Wu, and Jingbo Zhou. 2024. Frost: Fine-grained reward optimization for step-wise thinking. arXiv preprint arXiv:2403.00604. — [arXiv:2403.00604](https://arxiv.org/abs/2403.00604) find
  19. Jinhao Jiang, Kun Zhou, Xin Zhao, Yaliang Li, and Ji-Rong Wen. 2023. ReasoningLM: Enabling structural subgraph reasoning in pre-trained language models Xin Lai, Zhuotao Tian, Yukang Chen, Senqiao Yang, Xiangru Peng, and Jiaya Jia. 2024. Step-dpo: Step-wise preference optimization for long-chain reas…
  20. Harrison Lee, Samrat Phatale, Yuntao Bai, Xiang Lsmooth, Adam Gleave, Shixiang Shane Khan, Anna Chen, Dawn Drain, Deep Ganguli, Tom Henighan, and 1 others. 2023. RLAIF: Scaling Reinforcement Learning from Human Feedback with AI Feedback. arXiv preprint arXiv:2309.00267. find
  21. Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. 2023. Let’s verify step by step. arXiv preprint arXiv:2305.20050.
  22. Hui Lin and Jeff Bilmes. 2011. A class of submodular functions for document summarization. In Proceedings of the 49th annual meeting of the association for computational linguistics: human language technologies, pages 510–520.
  23. Runze Liu, Jiakang Wang, Yuling Shi, Zhihui Xie, Chenxin An, Kaiyan Zhang, Jian Zhao, Xiaodong Gu, Lei Lin, Wenping Hu, and 1 others. 2025a. Attention as a compass: Efficient exploration for process-supervised rl in reasoning models. arXiv preprint arXiv:2509.26628. — [arXiv:2509.26628](https://arxiv.org/abs/2509.26628) find
  24. Yihao Liu, Shuocheng Li, Lang Cao, Yuhang Xie, Mengyu Zhou, Haoyu Dong, Xiaojun Ma, Shi Han, and Dongmei Zhang. 2025b. Superrl: Reinforcement learning with supervision to boost language model reasoning. arXiv preprint arXiv:2506.01096. — [arXiv:2506.01096](https://arxiv.org/abs/2506.01096) find
  25. Meta AI. 2024. Llama 3.2 3b instruct — model card. https://huggingface.co/meta-llama/ Llama-3.2-3B-Instruct. Accessed 2025-10-07. ↗
  26. Microsoft. 2024. Phi-3.5 mini instruct — model card. https://huggingface.co/microsoft/ Phi-3.5-mini-instruct. Accessed 2025-10-07. ↗
  27. Microsoft Research Team. 2024. Phi-3 technical report: A highly capable language model locally trainable on consumer hardware. arXiv preprint arXiv:2404.14219.
  28. Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L Wainwright, Pavel Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, and 1 others. 2022. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, volume 35, pages…
  29. Ankit Pal, Logesh Kumar Umapathi, and Malaikannan Vazirani. 2022. Medmcqa: A large-scale multi-subject multi-choice question answering dataset for medical domain. In Proceedings of the Conference on Health, Inference, and Learning (CHIL), pages 248–260. find
  30. Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. 2023. Direct preference optimization: Your language model is secretly a reward model. Advances in neural information processing systems, 36:53728–53741.
  31. Qwen Team. 2024. Qwen2.5 technical report. arXiv preprint arXiv:2412.15115. find
  32. Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. 2022. Solving math word problems with process-and outcome-based feedback. arXiv preprint arXiv:2211.14275.
  33. Ashok Kumar Vijayakumar, Michael Cogswell, Ramprasaath R Selvaraju, Qing Sun, Stefan Lee, David Crandall, and Dhruv Batra. 2018. Diverse beam search for improved description of complex scenes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32. find
  34. Peiyi Wang, Lei Li, Zhihong Shao, R. X. Xu, Damai Dai, Yifei Li, Deli Chen, Y. Wu, and Zhifang Sui. 2023a. Math-shepherd: Verify and reinforce llms step-by-step without human annotations. arXiv preprint arXiv: 2312.08935.
  35. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023b. Self-consistency improves chain of thought reasoning in language models. In International Conference on Learning Representations (ICLR).
  36. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou. 2022. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, volume 35, pages 24824–24837.
  37. Marc’Aurelio Ranzato, Sumit Chopra, Michael Auli, and Wojciech Zaremba. 2015. Sequence level training with recurrent neural networks. arXiv preprint arXiv:1511.06732.
  38. Hanning Wu, Nan Jiang, Harrison Lee, Yuntao Bai, Andy Jones, and Adam Gleave. 2023. PRM800K: A Large-Scale Dataset of Process Reward Models. arXiv preprint arXiv:2310.04964. This is for a dataset of Process Reward Models. For the general concept, this or Lightman et al. can be used. — [arXiv:2310.04964](https://arxiv.org/abs/2310.04964) find
  39. Tal Schuster, Adam Fisch, Jai Gupta, Mostafa Dehghani, Dara Bahri, Vinh Tran, Yi Tay, and Donald Metzler. 2022. Confident adaptive language modeling. Advances in Neural Information Processing Systems, 35:17456–17472. find
  40. Ji Xin, Raphael Tang, Jaejun Lee, Yaoliang Yu, and Jimmy Lin. 2020. Deebert: Dynamic early exiting for accelerating bert inference. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 2246–2251.
  41. Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Y Wu, and 1 others. 2024. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300.
  42. Chenxu Yang, Qingyi Si, Yongjie Duan, Zheliang Zhu, Chenyu Zhu, Qiaowei Li, Zheng Lin, Li Cao, and Weiping Wang. 2025. Dynamic early exit in reasoning models. arXiv preprint arXiv:2504.15895. find
  43. Weijie Shi, Yue Cui, Yaguang Wu, Jingzhi Fang, Shibo Zhang, Mengze Li, Sirui Han, Jia Zhu, Jiajie Xu, and Xiaofang Zhou. 2025. Semantic-guided diverse decoding for large language model. arXiv preprint arXiv:2506.23601. — [arXiv:2506.23601](https://arxiv.org/abs/2506.23601) find
  44. Noam Shinn, Shinn Yao, Eric Zhao, Dian Li, Denny Zhou, Xuezhi Liu, and Percy Liang. 2023. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305.10601. find
  45. Adam Younsi, Abdalgader Abubaker, Mohamed El Amine Seddik, Hakim Hacid, and Salem Lahlou. 2025. Accurate and diverse llm mathematical reasoning via automated prm-guided gflownets. arXiv preprint arXiv:2504.19981. find
  46. Eric Zelikman, Qian Huang, Gabriel Poesia, Noah Goodman, and Nick Haber. 2023. Parsel: Algorithmic reasoning with language models by composing decompositions. Advances in Neural Information Processing Systems, 36:31466–31523. find
  47. Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. 2023. Automatic chain of thought prompting in large language models. In International Conference on Learning Representations (ICLR).
  48. Lianmin Zheng, Siyuan Zhuang, Zhewei Yao, Eric Wallace, Steven M. Drucker, Joseph E. Gonzalez, and Ion Stoica. 2022. Pal: Program-aided language models. arXiv preprint arXiv:2211.10435. find
  49. Ming Zhou, Yanzhao Chen, Yuntao Bai, and 1 others. 2023. Language models as task planners: A meta-reinforcement learning perspective. arXiv preprint arXiv:2311.05797. — [arXiv:2311.05797](https://arxiv.org/abs/2311.05797) find
  50. Yifei Zhou, Song Jiang, Yuandong Tian, Jason Weston, Sergey Levine, Sainbayar Sukhbaatar, and Xian Li. 2025. Sweet-rl: Training multi-turn llm agents on collaborative reasoning tasks. arXiv preprint arXiv:2503.15478. — [arXiv:2503.15478](https://arxiv.org/abs/2503.15478) find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/mishra-2026-sd-e2-semantic-exploration-reasoning/