Research map / Large language models / Reasoning and chain of thought
PENCIL: Long Thoughts with Short Memory
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PENCIL, an autoregressive generation scheme that interleaves token generation with a learned-pattern reduction rule that erases finished intermediate thoughts, enabling polynomial-memory long reasoning and proving universal space-efficient computation for transformers.
Problem
Chain-of-thought reasoning accumulates all intermediate computation in context, so memory grows with reasoning length, which limits solving computationally hard problems (SAT, QBF, Einstein's puzzle) under fixed context windows.
Approach
Add a reduction rule (inspired by function call stacks) with special tokens [CALL], [SEP], [RETURN] that deletes the intermediate thoughts of a completed sub-computation and keeps only its answer, applied repeatedly during autoregressive generation; training computes loss only on newly generated tokens per reduced sequence.
Key results
- On Einstein's 5x5 puzzle, PENCIL with a 25.19M-parameter model and 2048 context reaches 97% accuracy, while CoT drops to about 25%.
- On QBF at n=10, CoT accuracy falls to about 73% (per table) while PENCIL stays at 100%; max sequence length for QBF n=10 drops from 151,661 to 649 tokens.
- On SAT at n=10, CoT accuracy is 50% versus 100% for PENCIL.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PENCIL reduction instead of CoT | SAT · SAT n=10 | accuracy: 50 -> 100 | Helped |
| Use PENCIL reduction instead of CoT | QBF · QBF n=10 | accuracy: 73 -> 100 | Helped |
| Use PENCIL reduction instead of CoT | Einstein's puzzle · Einstein's puzzle 5×5 | accuracy: 25% -> 97% | Helped |
| Remove tail recursion (ablation) | PENCIL on Einstein's puzzle · Einstein's puzzle 5×5 | maximal sequence length: 3,335 -> 7,705 | Hurt |
Surprising findings
- Even when memory is not a bottleneck, PENCIL converges with fewer training FLOPs than CoT because shorter contexts make each token cheaper.
- A 25M-parameter transformer solves 5x5 Einstein's puzzle, a task where the paper says GPT-4 fails with few-shot CoT.
Limitations
- Experiments use small, synthetic, algorithmically generated tasks with models trained from scratch rather than pretrained LLMs.
- Requires supervised traces produced by a known algorithm to learn the reduction pattern.
- Theoretical results assume idealized transformer architecture choices (e.g., average-hard attention, Gated ReLU, positional embedding n->n).
Experimental setup
Datasets: synthetic 3-SAT instances (ratio 4.3) synthetic QBF instances synthetic Einstein's puzzle instances (3x3, 4x4, 5x5)
Benchmarks: 3-SAT (n=3-10) QBF (n=3-10) Einstein's puzzle 3x3, 4x4, 5x5
Metrics: accuracy trace rate inference time FLOPs-based convergence
Baselines: CoT GPT-4 few-shot CoT
Builds on: chain-of-thought RASP average-hard attention DPLL algorithm
Closest papers by meaning
- Analyzing the Power of Chain of Thought through Memorization Capabilities (NeurIPS 2025 · similarity 0.89)
- Making Slow Thinking Faster: Compressing LLM Chain-of-Thought via Step Entropy (ICLR 2026 · similarity 0.89)
- Let Me Think! A Long Chain of Thought Can Be Worth Exponentially Many Short Ones (NeurIPS 2025 · similarity 0.88)
- Reasoning with Latent Thoughts: On the Power of Looped Transformers (ICLR 2025 · similarity 0.87)
- Efficiently Representing Algorithms With Chain-of-Thought Transformers (NeurIPS 2026 · similarity 0.87)
- Demystifying Long Chain-of-Thought Reasoning (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.