연필 : 짧은 기억으로 긴 생각

OpenAi의 O1/O3, DeepSeek의 R1 및 Anthropic의 Claude 3.7과 같은 최근의 대형 언어 모델 (LLM)은 테스트 시간에 더 깊고 더 오래 생각할 수있게하면 모델의 추론 기능을 크게 향상시킬 수 있음을 보여줍니다.

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.

OpenAi의 O1/O3, DeepSeek의 R1 및 Anthropic의 Claude 3.7과 같은 최근의 대형 언어 모델 (LLM)은 테스트 시간에 더 깊고 더 오래 생각할 수있게하면 모델의 추론 기능을 크게 향상시킬 수 있음을 보여줍니다. 그들의 깊은 사고 능력의 기초가되는 핵심 접근법을 COT (Chain-of-Thought) (COT)라고하며, 모델은 중간 추론 단계를 반복적으로 생성하고 최종 답변을 생성 할 때까지 현재 상황에 추가합니다.

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:

그러나 작업이 점점 복잡해지면서 해결하는 데 필요한 단계는 극적으로 커집니다. 예를 들어, COT를 사용하여 NP-HARD 문제를 해결하는 것을 고려하십시오. 기본 모델 및 P ≠ NP로 고정 크기 변압기를 가정 할 때, 추론 추적은 필연적으로 지수 단계에 걸쳐 있습니다. 이것은 중요한 질문을 제기합니다.

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

COT 기반 테스트 시간 스케일링은 하드 천장에 도달합니까?

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.

불행히도 아마도 그렇습니다. (1) 체인은 필연적으로 모델의 컨텍스트 창을 초과하고, (2) 중요한 정보가 묻히고 수많은 이전 토큰에서 검색하기가 거의 불가능하며 (3) 자체 변환 복잡성으로 인해 각각의 새로운 토큰이 비싸게됩니다.

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.

이 기사에서, 우리는 이론적 및 실제적인 관점에서 현재 LLM 아키텍처를 지배하는 기존의 "쓰기 전용"COT 추론 패러다임에 도전합니다. 또한, 우리는 LLM이 생각을 생성 할뿐만 아니라 생각을 지울 수있는 근본적으로 다른 추론 접근법을 탐구 할 것입니다. 이러한 사고 삭제 능력은 성능과 효율성에서 중요한 실질적인 이점을 제공 할뿐만 아니라 계산 이론 관점에서 최적의 추론 효율성을 달성하는 데 기본이된다.

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.

이 게시물은 C. Yang et al.,“연필 : 짧은 기억을 가진 긴 생각”을 기반으로합니다. 머신 러닝에 관한 국제 컨퍼런스 2025, Nathan Srebro, David McAllester, Zhiyuan Li와의 협력. 코드도 사용할 수 있습니다.

Not Everything Needs to Be Remembered

모든 것을 기억할 필요는 없습니다

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.

정보를 선택적으로 폐기한다는 아이디어는 최초의 계산 모델에서 현대 시스템에 이르기까지 컴퓨터 과학 역사에 깊은 뿌리를두고 있습니다. 클래식 튜링 머신은 모든 상태를 보존하지 않고 테이프에 상징을 덮어 씁니다. 프로그래밍 언어는 함수가 실행을 완료 할 때 자동으로 릴리스되는 스택 프레임을 통해 메모리를 회수합니다. 그리고 현대적인 쓰레기 수집가는 더 이상 프로그램에 액세스 할 수없는 물체를 지속적으로 식별하고 제거합니다. 이러한 메커니즘은 단순히 효율성 최적화가 아니라 유한 리소스 내에서 복잡한 계산을 가능하게하는 필수 설계 선택이었습니다.

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.

이 아이디어는 또한 인간의 추론에도 적용됩니다. 정리 증명에서, 일단 레마가 확립되면, 우리는 결과를 보존하면서 상세한 파생을 폐기합니다. 문제 해결 접근법을 탐색 할 때, 우리는 비생산적인 경로를 전체 흔적을 유지하지 않고 "실패"로 표시합니다. 복잡한 추론을 통해 우리는 자연스럽게 정보를 압축하여 정보에 도달하는 데 사용 된 비계를 버리는 동안 결론을 유지합니다.

✏️ PENCIL: A New Reasoning Paradigm

✏️ 연필 : 새로운 추론 패러다임

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

따라서 우리는 LLM에 대한 새로운 추론 패러다임 인 ose️ 연필을 제안합니다. 생각 만 생성하는 ✒️ 코트와 달리 연필은 마지막 답변에 도달 할 때까지 재귀 적으로 생각을 생성하고 지 웁니다. 미래의 사고를 생성하는 데 필요한 최소한의 컨텍스트 만 유지하므로 모델은 더 짧고 깊은 작업 메모리를 사용하여 더 어려운 작업을 해결하기 위해 더 길고 깊이 생각할 수 있습니다. 다음 그림은 연필의 작동 방식을 보여줍니다

How Do Models Erase Thoughts?

모델은 어떻게 생각을 지우나요?

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.

연필의 삭제 메커니즘은 두 가지 고전적인 아이디어를 그립니다. 먼저, 논리 및 고전적인 자동화 된 정리 증명의 재 작성 규칙에서, 최종 답변에 도달 할 때까지 복잡한 논리적 또는 산술 표현을 표준 형태로 단순화하기 위해 사전 정의 된 규칙을 지속적으로 적용합니다. 둘째, 함수 프레임을 생성하는 기능 프로그래밍 언어에서 함수를 호출 할 때 로컬 변수를 저장하고 함수가 반환 될 때 해당 메모리를 릴리스하여 더 이상 필요하지 않은 중간 상태를 자동으로 폐기합니다.

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

구체적으로, 우리는 [Call], [Sep] 및 [return]이라는 3 개의 특수 토큰을 소개하고 다음 축소 규칙을 사용하여 Erasure를 구현합니다.

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.

C는 문맥을 나타내는 경우, T는 중간 사고를 의미하며 A는 대답을 나타냅니다. 생성 된 시퀀스가 ​​왼쪽의 패턴과 완전히 일치 할 때마다 연필은 감소 규칙을 트리거하여 생각을 지우고 대답을 맥락으로 다시 병합합니다. C, T 및 A CAN 자체는 특수 토큰을 포함하여 중첩 된 기능 호출과 유사한 재귀 구조를 지원한다는 점에 유의해야합니다. 예를 들어 C는 다른 [호출] 토큰을 포함 할 수 있으며, 이는 새로운 사고 서브 루틴이 시작되었음을 나타냅니다.

How to Use PENCIL?

연필을 사용하는 방법?

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

연필의 삭제 메커니즘은 다음과 같은 다양한 추론 패턴을 유연하게 지원합니다.

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꿀 : 작업 분해 : [호출]를 사용하여 하위 문제를 시작하고 중간 결과를 생성 한 다음 [SEP] 및 [리턴]을 사용하여 출력을 병합하고 하위 문제 추론 세부 사항을 지우십시오.

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️ack 분기 및 역 추적 : [Call], [Sep], [Return] Triplet을 사용하여 검색 트리의 탐사 브랜치를 관리하고 충돌이나 실패시 잘못된 경로를 지우는 것입니다.

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

3️ tail 요약 / 꼬리 재귀 : 긴 추론 추적을 간결한 요약으로 응축시켜 프로그래밍에서 꼬리 재귀 최적화와 유사하게 :

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

여기서 t는 원래 복잡한 추론 프로세스 (또는 더 어려운 문제)를 나타내고, t '는 요약 또는 단순화를 나타냅니다.