Can reasoning systems forget history without losing coherence?
Does treating each reasoning step as independent—rather than accumulating historical context—actually preserve problem-solving quality while reducing computational waste? This explores whether Markov-style memoryless reasoning can scale effectively.
Existing test-time scaling methods all carry history along. Chain-based methods preserve the entire reasoning trace to generate each next step. Tree-based methods track ancestor and sibling relationships across branches. Graph-based methods compound this with arbitrary node dependencies. As reasoning scales, the accumulated historical dependencies waste compute and — worse — interfere with the model's ability to reason effectively on the current state.
Atom of Thoughts (2502.12018) makes a different bet: each reasoning state should be a simplified problem equivalent to the original, with partial reasoning steps either transformed into known conditions or excluded as incorrect explorations. The state transition mechanism has two phases. First, decompose the current question into a dependency-based directed acyclic graph (DAG) capturing structural information. Second, contract the subquestions into a new independent question. Iterate the decomposition-contraction until reaching directly-solvable atomic questions.
The Markov property is the load-bearing claim. Each transition depends only on the current state — never on the path that produced it. This is not a heuristic; it is a structural property guaranteed by answer-equivalence preservation through contraction. If the contracted question yields the same answer as the original, no historical context is required to continue.
The cognitive science motivation is direct. Humans solve complex problems by identifying and resolving self-evident subquestions, then reformulating a simplified problem state — not by maintaining detailed reasoning processes for resolved components. The reformulation IS the memory management.
Two architectural advantages emerge. AoT eliminates the need for maintaining and computing historical information when scaling test-time compute, and atomic questions can be seamlessly integrated into existing TTS frameworks as a plug-in enhancement. Since Can recursive subtask trees overcome context window limits?, AoT is the language-level version of the same insight — TIMRUN prunes KV cache to free positional embeddings; AoT contracts subproblems to free conceptual context. Both reject the assumption that more history equals better reasoning.
Inquiring lines that read this note 108
This note is a source for these research framings, grouped by the broader line of inquiry each explores. Scan the bold lines of inquiry; follow any specific question forward.
How do we evaluate AI systems when user perception misleads actual performance? How does AI assistance affect human cognitive development and reasoning autonomy? Can AI-generated outputs constitute genuine knowledge or valid claims? Why do reasoning models fail at systematic problem-solving and search?- What design changes could make constraint inference more reliable without explicit cuing?
- Why does step-by-step reasoning fail when tool outputs get very large?
- What makes a background condition relevant to a specific reasoning task?
- When should a system decide to retrieve versus reason alone?
- Why do reasoning chains degenerate into undirected exploration at scale?
- Can explicit optimal algorithms prevent reasoning model collapse at high complexity?
- Can recursive sub-calls decompose reasoning across multiple context chunks?
- Can instance-adaptive reasoning happen without sequential token dependencies?
- Can bounded workspaces prevent overthinking better than summarization alone?
- Does irrelevant content degrade reasoning even when it fits the context window?
- Does irrelevant context degrade reasoning even within model context limits?
- How can prompt intervention reduce redundant reasoning steps dynamically?
- Can context compression preserve what matters without introducing bias?
- How does compressing memory between iterations prevent overthinking?
- When should architects prioritize consolidation compute over larger context windows?
- How do memory hierarchies and compression reduce context management demands?
- How does scene-switching prevent cross-problem interference in multi-agent reasoning?
- Does selective history retrieval outperform full context inclusion in agent reasoning?
- Does inference-time compute scaling require explicit reasoning traces or verifiable rewards?
- Can post-thinking compute on memory reduce query-time reasoning costs?
- How does precomputing context reasoning reduce latency in stateful applications?
- Can memory and test-time compute scale together as a single axis?
- Can test-time scaling work through retrieval rather than reasoning?
- What inference-time scaling benefits emerge from reasoning before each prediction?
- Can parallel thinking outperform sequential thinking under the same token budget?
- Does parallel sampling avoid failed-branch contamination more than sequential thinking?
- Can parallel independent reasoning outperform sequential iterative refinement?
- Can parallel reasoning chains outperform longer sequential chains with the same compute?
- Why does parallel thinking outperform sequential thinking under the same token budget?
- What makes parallel thinking more efficient than sequential chains?
- What makes a problem fundamentally sequential versus parallelizable?
- Are some problems fundamentally unsolvable by parallel inference methods?
- Does decoupling reasoning reduce inference cost more than sequential scaling?
- Why does parallel sampling become more efficient when reasoning branches are memoryless?
- Why do aggregation tasks degrade faster than multi-hop reasoning under sparsity?
- Can adaptive compute distribution across prompts replace the need for sophisticated reasoning frameworks?
- Can cost-aware stopping points cut computation without losing accuracy?
- When does explicit reasoning actually degrade performance on a task?
- Does reflection destabilize reasoning in dynamic environments?
- What role do cyclic fixed points play in stable reasoning?
- How do hierarchical architectures separate planning from retrieval differently than flat ones?
- How does separating decomposition from execution improve multi-step reasoning?
- Why do linear research pipelines lose global context across planning and generation steps?
- How does decoupling reasoning from tool observations improve parallel execution?
- Does algorithmic decomposition prevent planning-execution interference in reasoning?
- Why does decoupling planning from execution improve over sequential interleaving?
- How does decomposing tasks prevent interference between planning and execution?
- When does backward decomposition fail on open-ended or unstructured tasks?
- How does separating decomposition from execution improve multi-step reasoning accuracy?
- How should iterative research tasks limit context per reasoning turn?
- Why do long-horizon reasoning tasks need per-turn step limits rather than just compute budgets?
- Does unrestricted reasoning per search step degrade iterative quality over time?
- Can historical and batch exploration be implemented with the same algorithmic mechanism?
- Can stateless multi-step retrieval capture evidence integration as well as dynamic memory?
- Can layer-wise KV caches enable truly lossless information transfer?
- Can any architecture fundamentally solve problems that require inherently sequential computation?
- Does logical trace coherence guarantee valid mathematical reasoning?
- Why does the same recalled information lead to different reasoning conclusions?
- How does trace coherence differ from valid mathematical proof in practice?
- What makes answer equivalence sufficient to discard a reasoning path?
- What makes memory trajectories topologically stable under persistent reuse?
- What persistent memory architectures best support storing precomputed inferences across sessions?
- How does context budget create tradeoffs between memory and skills?
- What makes structured memory schemas more stable than freeform text summaries?
- How does separating local and global context dependencies affect long-context performance?
- What gets lost when we describe memory as retrieval?
- Can memory workspaces resolve contradictory evidence that stateless systems miss?
- Can models consolidate context into weights during idle offline phases?
- Does including full context always degrade memory retrieval quality in practice?
- How should memory systems handle deletion as a structural property?
- How do insert, forget, and merge operations maintain thought coherence over time?
- What distinguishes formation, evolution, and retrieval as separate memory dynamics?
- What makes timestamped knowledge repositories better than static memory?
- What discarding policy prevents both stale entries and loss of rare critical knowledge?
- What details do high-level trajectory abstractions lose that state-grounded recall preserves?
- Why does the hot-path cold-path split map onto formation and evolution?
- What computational cost does trajectory-bursty inference impose on per-query context requirements?
- When does active reconstruction cost more than simple context dumping?
- How does accumulated context history degrade iteration quality in long-horizon tasks?
- Why does a replay mechanism prevent reasoner skills from over-specializing?
- Why does structured stochasticity help reasoning more than naive randomness?
- Does compressing all past memories into one representation lose irretrievable details?
- Can episodic raw memory outperform consolidated summaries in practice?
- What makes naive memory consolidation regress below having no memory at all?
- Why does consolidating more state sometimes hurt performance below the no-memory baseline?
Related concepts in this collection 3
This note in its neighbourhood — explore the map, then jump to a related concept in the list below.
Click a node to walk · click center to open · click Open in graph to see this note in the full knowledge graph
-
Can recursive subtask trees overcome context window limits?
Explores whether modeling reasoning as prunable trees of subtasks could eliminate the context length constraints that currently force developers into multi-agent architectures. Asks if working memory can become truly unlimited through selective KV cache retention.
TIMRUN does the same at the KV-cache layer; AoT does it at the conceptual layer; both reject history-accumulating reasoning
-
Why does parallel reasoning outperform single chain thinking?
Does dividing a fixed token budget across multiple independent reasoning paths beat spending it all on one long chain? This explores how breadth and diversity in reasoning compare to depth.
AoT can compose with parallel sampling once each branch is memoryless
-
Do iterative refinement methods suffer from overthinking?
Iterative refinement approaches like Self-Refine structurally resemble token-level overthinking in o1-like models. Does revision across multiple inference calls reproduce the same accuracy degradation seen within single inferences?
AoT is the structural fix that PDR's bounded-workspace also targets: bounded state via contraction rather than via summarization
Related papers in this collection 8
Papers most semantically related to this note, ranked by cosine similarity in the embedding space.
- Atom of Thoughts for Markov LLM Test-Time Scaling
- Does Thinking More always Help? Understanding Test-Time Scaling in Reasoning Models
- Learning to Think: Information-Theoretic Reinforcement Fine-Tuning for LLMs
- The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity
- A Decomposition Perspective to Long-context Reasoning for LLMs
- A Comment On "The Illusion of Thinking": Reframing the Reasoning Cliff as an Agentic Gap
- Rethinking Thinking Tokens: LLMs as Improvement Operators
- Test-time Prompt Intervention
Original note title
markov-style memoryless reasoning replaces accumulated-history test-time scaling with iterative decompose-then-contract