{"id":3770,"date":"2025-05-13T07:02:33","date_gmt":"2025-05-13T07:02:33","guid":{"rendered":"https:\/\/mailitics.com\/index.php\/2025\/05\/13\/empowering-llms-to-think-deeper-by-erasing-thoughts\/"},"modified":"2025-05-13T07:02:33","modified_gmt":"2025-05-13T07:02:33","slug":"empowering-llms-to-think-deeper-by-erasing-thoughts","status":"publish","type":"post","link":"https:\/\/mailitics.com\/index.php\/2025\/05\/13\/empowering-llms-to-think-deeper-by-erasing-thoughts\/","title":{"rendered":"Empowering LLMs to Think Deeper by Erasing Thoughts"},"content":{"rendered":"

Empowering LLMs to Think Deeper by Erasing Thoughts
\n \t

\n
<\/BR>
\n
\n \t

\n
<\/BR><\/p>\n

\n

Introduction<\/mdspan><\/h2>\n

Recent large language models (LLMs)<\/strong> \u2014 such as OpenAI\u2019s o1\/o3<\/a>, DeepSeek\u2019s R1 and Anthropic\u2019s Claude 3.7 \u2014 demonstrate that allowing the model to think deeper and longer at test time can significantly enhance model\u2019s reasoning capability. The core approach underlying their deep thinking capability is called chain-of-thought (CoT)<\/a><\/strong>, where the model iteratively generates intermediate reasoning steps and appends them to the current context until producing the final answer.<\/p>\n

However, as tasks become increasingly complex, the steps needed to solve them grow dramatically. For instance, consider solving NP-hard problems using CoT \u2014 the reasoning trace would inevitably span exponential steps, assuming a fixed-size Transformer as the base model and P \u2260 NP.\u00a0This raises an important question:<\/p>\n

Will CoT-based test-time scaling hit hard ceilings? <\/em><\/strong><\/p>\n

Unfortunately, probably yes. Various limitations will emerge for harder tasks: (1)<\/strong> chains will inevitably exceed model\u2019s context windows, (2)<\/strong> critical information becomes buried and nearly impossible to retrieve from numerous preceding tokens, and\u00a0(3)<\/strong>\u00a0the self-attention complexity makes generating each new token prohibitively expensive.<\/p>\n

\"\"
Generated by ChatGPT, prompted by author<\/figcaption><\/figure>\n

In this article, we challenge the conventional \u201cwrite-only\u201d CoT reasoning paradigm that dominates current LLM architectures, from both theoretical and practical perspectives. Furthermore, we will explore a fundamentally different reasoning approach that allows LLM to not only generate thoughts, but also erase thoughts. This capacity for thought erasure not only offers significant practical benefits in performance and efficiency, but proves fundamental for achieving optimal reasoning efficiency from a computational theory perspective.<\/p>\n

This post is based on the paper C. Yang et al., \u201cPENCIL: Long thoughts with short memory\u201d<\/a><\/em> accepted in International Conference on Machine Learning<\/a> 2025, a collaboration with Nathan Srebro, David McAllester, Zhiyuan Li. Code<\/a> is also available.<\/p>\n

\"\"<\/figure>\n
\n

Not Everything Needs to Be Remembered<\/h2>\n

The idea of selectively discarding information has deep roots in computer science history, from the earliest computational models to modern systems. The classic Turing machine overwrites symbols on its tape rather than preserving every state; programming languages reclaim memory through stack frames that are automatically released when functions complete their execution; and modern garbage collectors continuously identify and remove objects no longer accessible to the program. These mechanisms weren\u2019t merely efficiency optimizations \u2014 they were essential design choices that made complex computation possible within finite resources.<\/p>\n

This idea also applies to human reasoning. In theorem proving, once a lemma is established, we discard its detailed derivation while preserving the result; when exploring problem-solving approaches, we simply mark unproductive paths as \u201cfailed\u201d without retaining their full traces. Throughout complex reasoning, we naturally compress information, retaining conclusions while discarding the scaffolding used to reach them.<\/p>\n

\n\"\u270f\" PENCIL: A New Reasoning Paradigm<\/h2>\n

Therefore, we propose \"\u270f\" PENCIL, a new reasoning paradigm for LLMs. Unlike \"\u2712\" CoT that only generates thoughts, PENCIL recursively generates and erases thoughts until reaching the final answer. It maintains only the minimal context required for generating future thoughts, so the model can think longer and deeper to solve harder tasks using shorter working memory. The following figure illustrates how PENCIL works<\/p>\n

\"\"
Chain-of-Thought (left) preserves all reasoning steps in context, creating lengthy outputs. PENCIL (right) alternates between generation (bold) and reduction (blue): discarding intermediate thoughts when no longer needed. After reaching the solution, PENCIL returns only the final answer, hiding the thinking process.<\/figcaption><\/figure>\n

How Do Models Erase Thoughts?<\/h3>\n

PENCIL\u2019s erasure mechanism draws on two classical ideas. First, from rewriting rules in logic and classical automated theorem proving<\/strong>, which continuously apply predefined rules to simplify complex logical or arithmetic expressions into canonical forms until reaching a final answer. Second, from functional programming languages<\/strong>, which creates stack frames to store local variables when calling functions and releases corresponding memory when functions return, automatically discarding intermediate states that are no longer needed.\u00a0<\/p>\n

Specifically, we introduce three special tokens, called [CALL], [SEP], and [RETURN], and use the following reduction rule to implement erasure:<\/p>\n

\"\"<\/figure>\n

where C <\/strong>stands for context, T <\/strong>stands for intermediate thoughts, and A <\/strong>stands for answer. Whenever the generated sequence completely matches the pattern on the left, PENCIL triggers the reduction rule, erasing thoughts and merging the answer <\/strong>back into the context. It is important to note that C<\/strong>, T<\/strong> and A<\/strong> can themselves contain special tokens, thereby supporting recursive<\/strong> structures similar to nested function calls \u2014 for example, C<\/strong> may contain another [CALL] token, indicating that a new thinking subroutine has been initiated.\u00a0<\/p>\n

How to Use PENCIL?<\/h3>\n

PENCIL\u2019s erasure mechanism flexibly supports various reasoning patterns, such as:<\/p>\n

1\u20e3 Task Decomposition<\/strong>: Using [CALL] to initiate subproblems, generate intermediate results, and then use [SEP] and [RETURN] to merge outputs and erase subproblem reasoning details;<\/p>\n

2\u20e3 Branch and Backtrack<\/strong>: Using a [CALL], [SEP], [RETURN] triplet to manage an exploration branch in a search tree, erasing invalid paths upon conflicts or failures.<\/p>\n

3\u20e3 Summarization \/ Tail Recursion<\/strong>: Condensing a lengthy reasoning trace into concise summary, similar to tail recursion optimization in programming:<\/p>\n

\"\"<\/figure>\n

where T<\/strong> represents the original complex reasoning process (or a more difficult problem), and T\u2019<\/strong> represents the summarized or simplified content (or an equivalent, more tractable problem).<\/p>\n

Example on a NP-Complete Task<\/h3>\n

For example, consider a classic NP-Complete problem Boolean Satisfiability (SAT): given a Boolean formula, determine whether there exists a variable assignment that makes it true. This problem is (widely believed to) require exponential time<\/strong> but only polynomial space<\/strong> to solve, with the simplest approach being traversing a binary search tree of depth n. <\/p>\n

Traditional CoT would accumulate intermediate calculations, causing the context length to grow proportionally with the number of nodes in the search tree, which is exponential time complexity of O(2^n). In comparison, PENCIL can recursively branch to try True\/False for a variable, backtracking upon conflict and erasing all thoughts within that branch. This thus keeps the context length proportional to the search depth, which is space complexity of only O(n).<\/p>\n

The following figure compares the maximum context length of the vanilla CoT without reduction (blue) and PENCIL with reduction (red). As problem complexity increases, PENCIL achieves dramatic space efficiency, notably reducing context length from 151,192 to just 3,335 tokens for Einstein\u2019s Puzzle.<\/p>\n

\"\"
Maximal sequence length with and without the reduction rule.<\/figcaption><\/figure>\n
\n

Training and Experiments<\/h2>\n

The core difference between CoT and PENCIL during training is the calculation of the loss function:<\/p>\n

\"\"<\/figure>\n
\"\"<\/figure>\n

For CoT, the loss for each new token is based on the complete historical context; for PENCIL, after each \u201cwrite-erase\u201d iteration, the model calculates loss for new tokens only on the reduced sequence. Although both generate the same number of tokens, PENCIL significantly shortens the context length corresponding to each token and thus is more efficient. <\/p>\n

It\u2019s also worthwhile to note that after each reduction, the KV cache for the shared prefix C<\/strong> can be directly reused, with only the cache for the shorter part A<\/strong> needing recalculation.\u00a0<\/p>\n

Experimental Results<\/h3>\n

Our experiments focus on three inherently hard reasoning tasks: 3-SAT (NP-Complete), QBF (PSPACE-Complete), and Einstein\u2019s Puzzle (natural language reasoning). For each task, we wrote a generator to generate a training set where special tokens are included. We train a small transformer (SAT\/QBF with 10.6M parameters; Einstein\u2019s Puzzle with 25.2M parameters) starting with random initialization for these tasks.<\/p>\n

\"\ud83d\udcca\" Compared to CoT, we found PENCIL can solve larger-scale reasoning problems. As shown in the figure below, in SAT (left) and QBF (right) tasks, when problem size is small, both CoT and PENCIL perfectly solve problems; but as size increases, traditional CoT accuracy drops significantly (e.g., only about 50% for SAT at n=10), while PENCIL maintains high accuracy \u2265 99%. This is primarily because CoT\u2019s context sequence length explodes exponentially, whereas PENCIL avoids explosion by dynamic reduction.<\/p>\n

\"\"
Performance comparison on 3-SAT (left) and QBF (right)<\/figcaption><\/figure>\n

\"\u26a1\" Additionally, PENCIL significantly saves computational resources. As shown in the figure, for QBF (n=3\u20136) tasks, we compared the convergence speed of CoT (blue) and PENCIL (red) under the same FLOPs budget. PENCIL quickly reaches 100% accuracy while CoT, due to continuously expanding context length, requires more FLOPs to approach optimality. As the problem size increases, the gap between the two becomes more pronounced.<\/p>\n

\"\"
Comparison of convergence speed for training on the QBF problem (with n ranges from 3
to 6). Circles and vertical lines indicate the first time each method reaches optimal performance.<\/figcaption><\/figure>\n

\"\ud83e\udde9\" We further considered a very difficult logical reasoning problem: Einstein\u2019s Puzzle<\/a>. Each problem consists of 5 houses and 5 attribute categories of people living in them \u2014 color, nationality, drink, cigarette, and pet (e.g., Red\/Green\/Blue, Brit\/German\/Swede, Bird\/Dog\/Fish, etc.). Given clues like \u201cthe green house is right next to the bird owner\u2019s\u201d and \u201cthe dog owner lives in the red house,\u201d the task is to deduce \u201cwho owns the fish?\u201d This problem presents an extreme challenge for existing LLMs: even GPT-4 struggles to solve it<\/a>. The figure below shows a simplified version with only 3 houses and 3 attribute categories:<\/p>\n

\"\"
Illustration of Einstein\u2019s Puzzle.<\/figcaption><\/figure>\n

As shown below, for this problem that even large models struggle with, PENCIL achieves 97% accuracy using only a small 25.2M parameter model, while traditional CoT achieves only 25% accuracy (close to random guessing).<\/p>\n

\"\"
Performance on Einstein\u2019s Puzzle<\/figcaption><\/figure>\n
\n

Theory: Universal Efficient Computation<\/h2>\n

We further demonstrate PENCIL\u2019s fundamental advantage over traditional CoT from the theoretical expressive power <\/strong>perspective: PENCIL is Turing complete with optimal space complexity, and thus can solve arbitrary computable tasks efficiently. This is something fundamentally impossible for CoT!<\/p>\n

Main Results<\/h3>\n

Specifically, we prove: Using a fixed, finite-sized Transformer, PENCIL can simulate any Turing machine with optimal time and space complexity, thereby efficiently solving all computable problems.<\/em><\/p>\n

\"\"<\/figure>\n

In other words, for any Turing machine running in T time and S space, PENCIL requires only O(T) tokens while maintaining a maximum context length of O(S) to produce identical results. While previous work<\/a> established that traditional CoT can make Transformers Turing complete, it demands O(T) context length with each token representing an intermediate computation step. This distinction between maximum context length becomes crucial because for most algorithms, space complexity S is substantially smaller than time complexity T, especially for harder problems.<\/p>\n

Consider NP-Complete problems like Traveling Salesman or Hamiltonian Circuit, which are widely believed to require exponential time but solvable in polynomial space. Traditional CoT cannot solve these within polynomial context length constraints, and requires at least exponential length that exceeds practical memory limitations of any real system. PENCIL, in contrast, can solve them using only polynomial maximum context length, making previously intractable reasoning tasks feasible.<\/p>\n

Proof Sketch<\/h3>\n

We now briefly introduce our proof idea, where the key insight is to have PENCIL use a series of \u201cSimulation-Summarization\u201d iterations to clean the memory.<\/p>\n

\"\"
PENCIL simulates Turing machine iteratively using two phases: simulating computation steps from the previous state, and summarizing into the new state using the reduction rule.<\/figcaption><\/figure>\n

Step 1: Using CoT to Encode Turing Machine Transitions\u00a0 <\/strong>As illustrated in the left part of the figure above, we encode each Turing machine state transition as a token encoding \u201cnew state\u201d, \u201cwritten symbol\u201d, and \u201chead movement direction\u201d triplet in the embedding. The model can use self-attention to calculate the current head position and determine the symbol at this position. Without reduction, this process generates T tokens with context length O(T).<\/p>\n

Step 2: Alternating \u201cSimulation-Summarization\u201d\u00a0 <\/strong>PENCIL achieves space\/time optimality through alternating:<\/p>\n

    \n
  1. \nSimulation<\/strong>: Continuously generate Turing machine state transition tokens, simulating multiple computation steps;<\/li>\n
  2. \nSummarization<\/strong>: When new tokens exceed twice the space needed, summarize the computation using S tokens. The reduction rule then discards previous thoughts, keeping only the latest Turing machine state for the next round.<\/li>\n<\/ol>\n

    This strategy maintains total token generation at O(T) while limiting context length to O(S).<\/p>\n

    Step 3: Transformer Implementation <\/strong>To prove this process can be implemented by Transformers, we developed the Full-Access Sequence Processing (FASP) programming language and proved that any algorithm written in FASP can be implemented by a fixed-sized Transformer. In a FASP program, each variable corresponds to a Transformer sub-module, and each line of code transforms existing variables to a new variable through predefined functions, which is equivalent to constructing a more complex Transformer based on sub-modules. The variable returned by the program is the desired Transformer that encodes the algorithm. We wrote a FASP program that implements the \u201cSimulation-Summarization\u201d operation, which implies there exists a constant-sized Transformer that can perform the same function<\/p>\n

    \n

    Conclusion<\/h2>\n

    In conclusion, we propose a new reasoning paradigm PENCIL, which alternates between generation and erasure, and enables models to think deeper to solve more complicated problems. Theoretically, we prove that PENCIL achieves Turing completeness with optimal time and space efficiency and thus can efficiently solve any computable problems. Looking forward, a promising direction would be to fine-tune LLMs to incorporate PENCIL\u2019s memory-efficient reasoning capabilities. We hope these findings will inspire reexamining current reasoning models from the perspective of theory of computation.<\/p>\n

    \"\"<\/figure>\n

    \n

    The post Empowering LLMs to Think Deeper by Erasing Thoughts<\/a> appeared first on Towards Data Science<\/a>.<\/p>\n<\/div>\n

    \t

    \n
    <\/BR>
    \n Chenxiao Yang
    \n \t

    \n
    <\/BR>
    \n    Go to original source<\/a>
    \n \t

    \n
    <\/BR><\/p>\n","protected":false},"excerpt":{"rendered":"

    Empowering LLMs to Think Deeper by Erasing Thoughts Introduction Recent large language models (LLMs) \u2014 such as OpenAI\u2019s o1\/o3, DeepSeek\u2019s R1 and Anthropic\u2019s Claude 3.7 \u2014 demonstrate that allowing the model to think deeper and longer at test time can significantly enhance model\u2019s reasoning capability. The core approach underlying their deep thinking capability is called […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[62,69,1030,67,71,87,70],"tags":[103,1400,2655],"class_list":["post-3770","post","type-post","status-publish","format-standard","hentry","category-aimldsaimlds","category-artificial-intelligence","category-chain-of-thought","category-deep-dives","category-large-language-models","category-llm","category-machine-learning","tag-model","tag-reasoning","tag-thoughts"],"_links":{"self":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/3770"}],"collection":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/comments?post=3770"}],"version-history":[{"count":0,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/posts\/3770\/revisions"}],"wp:attachment":[{"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/media?parent=3770"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/categories?post=3770"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mailitics.com\/index.php\/wp-json\/wp\/v2\/tags?post=3770"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}