mlsanityData to 7 Oct 2026

PENCIL: Long Thoughts with Short Memory

arXiv 2503.14337 ↗First posted 18 Mar 2025cs.LG cs.CLcited by 31

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

Abstract (arXiv)

While state-of-the-art LLMs have demonstrated great promise of using long Chains-of-Thought (CoT) to boost reasoning, scaling it up to more challenging problems at test-time is fundamentally limited by suboptimal memory usage -- intermediate computations accumulate indefinitely in context even when no longer needed for future thoughts. We introduce PENCIL, which incorporates a novel reduction mechanism into the autoregressive generation process that recursively cleans up intermediate thoughts based on patterns learned from training. By iteratively generating and erasing thoughts, PENCIL can think deeper to solve harder problems using shorter context and less compute. Empirically, we observe PENCIL is significantly more effective and efficient than CoT. For example, we demonstrate PENCIL with a small 25M-parameter transformer and 2048 context length solves Einstein's puzzle -- a task that challenges much larger models like GPT-4. Theoretically, we prove PENCIL can perform universal efficient computation by simulating any Turing machines with optimal time and space complexity, and thus can solve arbitrary computable tasks that are otherwise intractable for vanilla CoT.

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 28 of its 57 references that are in the map. First posted on arXiv 18 Mar 2025.

Builds on

28 of 57 references.

Closest ancestors · 5

Same direction, newest first

  1. 2024On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning20 Jun
  2. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems20 Feb
  3. 2023The Expressive Power of Transformers with Chain of Thought11 Oct
  4. 2022Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks22 Nov
  5. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Models21 May

Other references · 23

  1. 2020Scaling Laws for Neural Language Modelscited by 6,411
  2. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,146
  3. 2020Longformer: The Long-Document Transformercited by 3,362
  4. 2022Training Compute-Optimal Large Language Modelscited by 2,927
  5. 2021Efficiently Modeling Long Sequences with Structured State Spacescited by 2,424
  6. 2023Retrieval-Augmented Generation for Large Language Models: A Surveycited by 2,185
  7. 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,928
  8. 2020GLU Variants Improve Transformercited by 1,724
  9. 2020Reformer: The Efficient Transformercited by 1,658
  10. 2020Rethinking Attention with Performerscited by 1,584
  11. 2025s1: Simple test-time scalingcited by 1,311
  12. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 871
11 more
  1. 2024SnapKV: LLM Knows What You are Looking for Before Generationcited by 848
  2. 2022Decomposed Prompting: A Modular Approach for Solving Complex Taskscited by 554
  3. 2023LLMLingua: Compressing Prompts for Accelerated Inference of Large Language Modelscited by 279
  4. 2023Large Language Model Guided Tree-of-Thoughtcited by 218
  5. 2017Searching for Activation Functionscited by 158
  6. 2024Meta-Prompting: Enhancing Language Models with Task-Agnostic Scaffoldingcited by 115
  7. 2024Dynamic Memory Compression: Retrofitting LLMs for Accelerated Inferencecited by 115
  8. 2023Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Modelscited by 92
  9. 2024LazyLLM: Dynamic Token Pruning for Efficient Long Context LLM Inferencecited by 70
  10. 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
  11. 2024Memory makes computation universal, remember?cited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 11; 2026: 20.

31 papers.

Sort:

By area:

  1. 2025A Survey of Efficient Reasoning for Large Reasoning Models: Language, Multimodality, and Beyondcited by 131
  2. 2025Efficient Reasoning Models: A Surveycited by 93
  3. 2025Learning Adaptive Parallel Reasoning with Language Modelscited by 58
  4. 2025Scaling LLM Multi-turn RL with End-to-end Summarization-based Context Managementcited by 51
  5. 2025Multiverse: Your Language Models Secretly Decide How to Parallelize and Merge Generationcited by 30
  6. 2025Constant Bit-size Transformers Are Turing Completecited by 19
  7. 2026MEMENTO: Teaching LLMs to Manage Their Own Contextcited by 16
  8. 2025Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Onescited by 12
  9. 2025SPRINT: Enabling Interleaved Planning and Parallelized Execution in Reasoning Modelscited by 10
  10. 2026Recursive Models for Long-Horizon Reasoningcited by 9
  11. 2025On Learning Verifiers and Implications to Chain-of-Thought Reasoningcited by 6
  12. 2025Efficient Turing Machine Simulation with Transformerscited by 4
19 more
  1. 2026Do LLMs Benefit From Their Own Words?cited by 4
  2. 2026Reasoning Shift: How Context Silently Shortens LLM Reasoningcited by 3
  3. 2026Null Space Constrained Contrastive Visual Forgetting for MLLM Unlearningcited by 3
  4. 2026ECHO: Prune To Act, Trace To Learn With Selective Turn Memory In Agentic RLcited by 3
  5. 2025Fishing for Answers: Exploring One-shot vs. Iterative Retrieval Strategies for Retrieval Augmented Generationcited by 2
  6. 2026Chain-of-Thought and Compressed Looped Transformers: A Memory-Budget Separationcited by 2
  7. 2026Tight Sample Complexity of Transformerscited by 2
  8. 2026Modularized Reinforcement Learning on LLMs: From MDP Creation to Exploration and Learningcited by 2
  9. 2026Divide-and-Conquer CoT: RL for Reducing Latency via Parallel Reasoningcited by 1
  10. 2026Training Transformers as a Universal Computercited by 1
  11. 2026Taming the Thinker: Conditional Entropy Shaping for Adaptive LLM Reasoningcited by 1
  12. 2026Stateful Reasoning via Insight Replaycited by 0
  13. 2026The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thoughtcited by 0
  14. 2026Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Completecited by 0
  15. 2026The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thoughtcited by 0
  16. 2026Structured Thoughts For Improved Reasoning And Context Pruningcited by 0
  17. 2026MoNe: Modular Neural Memory for Efficient Long Context Inferencecited by 0
  18. 2026Recursive Language Models Generalize Out of Domaincited by 0
  19. 2026Understanding Generalization Requires Universal Inductioncited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Latent Reasoning with Supervised Thinking States
  2. 2025Early Stopping Chain-of-thoughts in Large Language Models
  3. 2025Long or short CoT? Investigating Instance-level Switch of Large Reasoning Models
  4. 2025Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoning
  5. 2025Analyzing the Power of Chain of Thought through Memorization Capabilities
  6. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective
  7. 2025Making Slow Thinking Faster: Compressing LLM Chain-of-Thought via Step Entropy
  8. 2025Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models