Crayon: longues pensées avec une mémoire courte

Les modèles récents de grande langue (LLMS) - tels que O1 / O3 d'OpenAI, R1 de Deepseek et Claude 3.7 d'Anthropic - démontrent que permettant au modèle de penser plus profondément et plus longtemps au moment du test peut améliorer considérablement la capacité de raisonnement du modèle.

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

Des modèles récents de grande langue (LLMS) - tels que O1 / O3 d'OpenAI, R1 de Deepseek et Claude 3.7 d'Anthropic - démontrent que permettant au modèle de penser plus profondément et plus longtemps au moment du test peut améliorer considérablement la capacité de raisonnement du modèle. L'approche centrale sous-jacente à leur capacité de pensée profonde est appelée chaîne de pensées (COT), où le modèle génère itérativement les étapes de raisonnement intermédiaire et les ajoute au contexte actuel jusqu'à la production de la réponse finale.

However, as tasks become increasingly complex, the steps needed to solve them grow dramatically. For instance, consider solving NP-hard problems using CoT — the reasoning trace would inevitably span exponential steps, assuming a fixed-size Transformer as the base model and P ≠ NP. This raises an important question:

Cependant, à mesure que les tâches deviennent de plus en plus complexes, les étapes nécessaires pour les résoudre augmenter considérablement. Par exemple, envisagez de résoudre les problèmes NP-durs en utilisant le COT - la trace de raisonnement couvrait inévitablement les étapes exponentielles, en supposant un transformateur de taille fixe comme modèle de base et p ≠ np. Cela soulève une question importante:

Will CoT-based test-time scaling hit hard ceilings?

La mise à l'échelle du temps de test basée sur le COT aura-t-elle atteint des plafonds durs?

Unfortunately, probably yes. Various limitations will emerge for harder tasks: (1) chains will inevitably exceed model’s context windows, (2) critical information becomes buried and nearly impossible to retrieve from numerous preceding tokens, and (3) the self-attention complexity makes generating each new token prohibitively expensive.

Malheureusement, probablement oui. Diverses limites émergeront pour des tâches plus difficiles: (1) les chaînes dépasseront inévitablement les fenêtres de contexte du modèle, (2) les informations critiques deviendront enterrées et presque impossibles à récupérer de nombreux jetons précédents, et (3) la complexité d'auto-assistance rend la génération de chaque nouveau jeton prohibitive.

In this article, we challenge the conventional “write-only” 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.

Dans cet article, nous remettant en question le paradigme conventionnel de raisonnement «en écriture sur l'écriture uniquement» qui domine les architectures LLM actuelles, à la fois des perspectives théoriques et pratiques. De plus, nous explorerons une approche de raisonnement fondamentalement différente qui permet à LLM de générer non seulement des pensées, mais aussi d'effacer les pensées. Cette capacité d'effacement de la réflexion offre non seulement des avantages pratiques importants en matière de performance et d'efficacité, mais s'avère fondamentale pour obtenir une efficacité de raisonnement optimale du point de vue de la théorie de la calcul.

This post is based on the paper C. Yang et al., “PENCIL: Long thoughts with short memory” accepted in International Conference on Machine Learning 2025, a collaboration with Nathan Srebro, David McAllester, Zhiyuan Li. Code is also available.

Cet article est basé sur l'article C. Yang et al., «Crayon: longues pensées avec une mémoire courte» acceptée dans la Conférence internationale sur l'apprentissage automatique 2025, une collaboration avec Nathan Srebro, David McAllester, Zhiyuan Li. Le code est également disponible.

Not Everything Needs to Be Remembered

Tout ne doit pas être rappelé

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’t merely efficiency optimizations — they were essential design choices that made complex computation possible within finite resources.

L'idée de rejeter sélectivement les informations a des racines profondes dans l'histoire de l'informatique, des premiers modèles de calcul aux systèmes modernes. La machine Turing classique écrase les symboles sur sa bande plutôt que de préserver chaque état; Les langages de programmation récupérent la mémoire via des trames de pile qui sont automatiquement libérées lorsque les fonctions terminent leur exécution; et les collectionneurs de déchets modernes identifient et suppriment en continu les objets qui ne sont plus accessibles au programme. Ces mécanismes n'étaient pas simplement des optimisations d'efficacité - c'étaient des choix de conception essentiels qui ont rendu le calcul complexe possible dans les ressources finies.

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 “failed” without retaining their full traces. Throughout complex reasoning, we naturally compress information, retaining conclusions while discarding the scaffolding used to reach them.

Cette idée s'applique également au raisonnement humain. Dans le théorème prouvant, une fois qu'un lemme est établi, nous supprimons sa dérivation détaillée tout en préservant le résultat; Lors de l'exploration des approches de résolution de problèmes, nous marquons simplement les voies improductives comme «échouées» sans conserver leurs traces complètes. Tout au long du raisonnement complexe, nous compressons naturellement des informations, conservant des conclusions tout en rejetant l'échafaudage utilisé pour les atteindre.

✏️ PENCIL: A New Reasoning Paradigm

✏️ Crayon: un nouveau paradigme de raisonnement

Therefore, we propose ✏️ PENCIL, a new reasoning paradigm for LLMs. Unlike ✒️ 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

Par conséquent, nous proposons le crayon ✏️, un nouveau paradigme de raisonnement pour les LLM. Contrairement au COT ✒️ qui ne génère des pensées, le crayon génère et efface les pensées jusqu'à atteindre la réponse finale. Il ne conserve que le contexte minimal requis pour générer des pensées futures, de sorte que le modèle peut penser plus longtemps et plus profondément pour résoudre des tâches plus difficiles en utilisant la mémoire de travail plus courte. La figure suivante illustre comment fonctionne le crayon

How Do Models Erase Thoughts?

Comment les modèles effacent-ils les pensées?

PENCIL’s erasure mechanism draws on two classical ideas. First, from rewriting rules in logic and classical automated theorem proving, 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, 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.

Le mécanisme d'effacement du crayon s'appuie sur deux idées classiques. Premièrement, à partir des règles de réécriture dans la logique et la preuve du théorème automatisé classique, qui applique en continu des règles prédéfinies pour simplifier les expressions logiques ou arithmétiques complexes dans des formes canoniques jusqu'à atteindre une réponse finale. Deuxièmement, à partir des langages de programmation fonctionnelle, qui crée des trames de pile pour stocker des variables locales lors de l'appel des fonctions et libère la mémoire correspondante lorsque les fonctions reviennent, éliminant automatiquement les états intermédiaires qui ne sont plus nécessaires.

Specifically, we introduce three special tokens, called [CALL], [SEP], and [RETURN], and use the following reduction rule to implement erasure:

Plus précisément, nous introduisons trois jetons spéciaux, appelés [Call], [Sep] et [Retour], et utilisons la règle de réduction suivante pour mettre en œuvre l'effacement:

where C stands for context, T stands for intermediate thoughts, and A 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 back into the context. It is important to note that C, T and A can themselves contain special tokens, thereby supporting recursive structures similar to nested function calls — for example, C may contain another [CALL] token, indicating that a new thinking subroutine has been initiated.

Là où C signifie contexte, t signifie des pensées intermédiaires et une réponse. Chaque fois que la séquence générée correspond complètement au motif de gauche, le crayon déclenche la règle de réduction, effaçant les pensées et fusionnant la réponse dans le contexte. Il est important de noter que C, T et A CAN contiennent eux-mêmes des jetons spéciaux, soutenant ainsi des structures récursives similaires aux appels de fonction imbriqués - par exemple, C peut contenir un autre jeton [d'appel], indiquant qu'un nouveau sous-programme de réflexion a été initié.

How to Use PENCIL?

Comment utiliser le crayon?

PENCIL’s erasure mechanism flexibly supports various reasoning patterns, such as:

Le mécanisme d'effacement du crayon soutient de manière flexible divers motifs de raisonnement, tels que:

1️⃣ Task Decomposition: Using [CALL] to initiate subproblems, generate intermediate results, and then use [SEP] and [RETURN] to merge outputs and erase subproblem reasoning details;

1️⃣ Décomposition de la tâche: Utilisation de [appel] pour initier des sous-problèmes, générer des résultats intermédiaires, puis utiliser [Sep] et [retour] pour fusionner les sorties et effacer les détails du raisonnement sous-problème;

2️⃣ Branch and Backtrack: Using a [CALL], [SEP], [RETURN] triplet to manage an exploration branch in a search tree, erasing invalid paths upon conflicts or failures.

2️⃣ Branche et retour en arrière: en utilisant un [appel], [Sep], [retour] triplet pour gérer une branche d'exploration dans un arbre de recherche, effaçant les chemins non valides lors des conflits ou des échecs.

3️⃣ Summarization / Tail Recursion: Condensing a lengthy reasoning trace into concise summary, similar to tail recursion optimization in programming:

3️⃣ Résumé / Récursion de la queue: Condensation d'une longue trace de raisonnement en résumé concis, similaire à l'optimisation de la récursivité de la queue dans la programmation:

where T represents the original complex reasoning process (or a more difficult problem), and T' represents the summarized or simplified

où t représente le processus de raisonnement complexe d'origine (ou un problème plus difficile), et t 'représente le résumé ou simplifié