# PENCIL: Long Thoughts with Short Memory

arXiv: https://arxiv.org/abs/2503.14337 · HTML: https://mlsanity.com/paper/2503.14337/

## Key facts

- Cited by 33 papers in the map (data through 14 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.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 28 of 28)

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Retrieval-Augmented Generation for Large Language Models: A Survey](https://mlsanity.com/paper/2312.10997/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [GLU Variants Improve Transformer](https://mlsanity.com/paper/2002.05202/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [Decomposed Prompting: A Modular Approach for Solving Complex Tasks](https://mlsanity.com/paper/2210.02406/) (2022)
- [LLMLingua: Compressing Prompts for Accelerated Inference of Large Language Models](https://mlsanity.com/paper/2310.05736/) (2023)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Large Language Model Guided Tree-of-Thought](https://mlsanity.com/paper/2305.08291/) (2023)
- [Searching for Activation Functions](https://mlsanity.com/paper/1710.05941/) (2017)
- [Meta-Prompting: Enhancing Language Models with Task-Agnostic Scaffolding](https://mlsanity.com/paper/2401.12954/) (2024)
- [Dynamic Memory Compression: Retrofitting LLMs for Accelerated Inference](https://mlsanity.com/paper/2403.09636/) (2024)
- [Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models](https://mlsanity.com/paper/2308.10379/) (2023)
- [LazyLLM: Dynamic Token Pruning for Efficient Long Context LLM Inference](https://mlsanity.com/paper/2407.14057/) (2024)
- [The Expressive Power of Transformers with Chain of Thought](https://mlsanity.com/paper/2310.07923/) (2023)
- [Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers](https://mlsanity.com/paper/2404.04393/) (2024)
- [On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning](https://mlsanity.com/paper/2406.14197/) (2024)
- [Memory makes computation universal, remember?](https://mlsanity.com/paper/2412.17794/) (2024)

## Built on by (most cited first, 30 of 33)

- [A Survey of Efficient Reasoning for Large Reasoning Models: Language, Multimodality, and Beyond](https://mlsanity.com/paper/2503.21614/) (2025)
- [Efficient Reasoning Models: A Survey](https://mlsanity.com/paper/2504.10903/) (2025)
- [Learning Adaptive Parallel Reasoning with Language Models](https://mlsanity.com/paper/2504.15466/) (2025)
- [Scaling LLM Multi-turn RL with End-to-end Summarization-based Context Management](https://mlsanity.com/paper/2510.06727/) (2025)
- [Multiverse: Your Language Models Secretly Decide How to Parallelize and Merge Generation](https://mlsanity.com/paper/2506.09991/) (2025)
- [Constant Bit-size Transformers Are Turing Complete](https://mlsanity.com/paper/2506.12027/) (2025)
- [MEMENTO: Teaching LLMs to Manage Their Own Context](https://mlsanity.com/paper/2604.09852/) (2026)
- [Let Me Think! A Long Chain-of-Thought Can Be Worth Exponentially Many Short Ones](https://mlsanity.com/paper/2505.21825/) (2025)
- [SPRINT: Enabling Interleaved Planning and Parallelized Execution in Reasoning Models](https://mlsanity.com/paper/2506.05745/) (2025)
- [Recursive Models for Long-Horizon Reasoning](https://mlsanity.com/paper/2603.02112/) (2026)
- [On Learning Verifiers and Implications to Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.22650/) (2025)
- [Do LLMs Benefit From Their Own Words?](https://mlsanity.com/paper/2602.24287/) (2026)
- [Efficient Turing Machine Simulation with Transformers](https://mlsanity.com/paper/2512.00003/) (2025)
- [Reasoning Shift: How Context Silently Shortens LLM Reasoning](https://mlsanity.com/paper/2604.01161/) (2026)
- [Null Space Constrained Contrastive Visual Forgetting for MLLM Unlearning](https://mlsanity.com/paper/2605.05909/) (2026)
- [The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought](https://mlsanity.com/paper/2605.18079/) (2026)
- [ECHO: Prune To Act, Trace To Learn With Selective Turn Memory In Agentic RL](https://mlsanity.com/paper/2606.31650/) (2026)
- [Fishing for Answers: Exploring One-shot vs. Iterative Retrieval Strategies for Retrieval Augmented Generation](https://mlsanity.com/paper/2509.04820/) (2025)
- [Chain-of-Thought and Compressed Looped Transformers: A Memory-Budget Separation](https://mlsanity.com/paper/2605.30757/) (2026)
- [Tight Sample Complexity of Transformers](https://mlsanity.com/paper/2606.09731/) (2026)
- [Modularized Reinforcement Learning on LLMs: From MDP Creation to Exploration and Learning](https://mlsanity.com/paper/2606.21943/) (2026)
- [The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought](https://mlsanity.com/paper/2607.07423/) (2026)
- [Divide-and-Conquer CoT: RL for Reducing Latency via Parallel Reasoning](https://mlsanity.com/paper/2601.23027/) (2026)
- [Training Transformers as a Universal Computer](https://mlsanity.com/paper/2604.25166/) (2026)
- [Taming the Thinker: Conditional Entropy Shaping for Adaptive LLM Reasoning](https://mlsanity.com/paper/2605.19358/) (2026)
- [Stateful Reasoning via Insight Replay](https://mlsanity.com/paper/2605.14457/) (2026)
- [Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete](https://mlsanity.com/paper/2606.01532/) (2026)
- [Structured Thoughts For Improved Reasoning And Context Pruning](https://mlsanity.com/paper/2607.10386/) (2026)
- [MoNe: Modular Neural Memory for Efficient Long Context Inference](https://mlsanity.com/paper/2608.17616/) (2026)
- [Recursive Language Models Generalize Out of Domain](https://mlsanity.com/paper/2609.20831/) (2026)

## 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.