Research map / Large language models / Agents, code and math
Encoder of Thoughts: Enhancing Planning Ability in Language Agents Through Structural Embedding
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 Encoder of Thoughts (EoT), a GNN-based graph transformer that encodes planning action graphs into special token embeddings fed to LLM agents, improving BFS/MCTS planning on GSM8K, MATH, and Blockworlds.
Problem
Complex reasoning structures used by planning-based prompting (ToT, GoT, RAP) exceed LLMs' ability to process and comprehend them, and describing graphs in natural language inflates token cost and confusion.
Approach
Encode the action graph with a graph transformer and project node-level structural embeddings into the LLM input space as soft tokens, so the generator and evaluator in search algorithms (BFS/MCTS) see compact structural information instead of textual paths; the encoder is trained on LLM-generated (Llama3-8B + ToT-style BFS) data.
Key results
- On GSM8K with Llama-3 8B, EoT-MCTS reaches 88.3% vs 82.2% for RAP-MCTS(5) and 71.5% for CoT (Table 2).
- On MATH with Llama-3 8B, EoT-MCTS(8) achieves 37.4% accuracy vs 28.2% for CoT and 34.6% for BFS.
- On Blockworlds 4-step tasks with Llama, EoT-BFS improves over ToT-BFS from 78.9% to 90.8%-style gains reported as +7.8% to +13.4% relative.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use EoT structural embeddings with BFS rather than the corresponding baseline | Language agents · GSM8K | accuracy: 0.4% in BFS | Helped |
| Use EoT structural embeddings with MCTS rather than the corresponding baseline | Language agents · GSM8K | accuracy: 5.0% in MCTS | Helped |
| Replace EoT embeddings with textual graph descriptions (ablation) | Existing reasoning methods · GSM8K | accuracy | Hurt |
| Replace graph-transformer GNN with GCN (ablation) | EoT-MCTS · GSM8K | accuracy | No clear effect |
| Remove the projection layer (ablation) | EoT-MCTS · GSM8K | accuracy | Hurt |
| Remove the GNN (ablation) | EoT-MCTS · GSM8K | accuracy | Hurt |
| Add all EoT paths as in-context demonstrations (ablation) | CoT · GSM8K | accuracy: 68.5 -> 71.6 | Helped |
| Add random EoT paths as in-context demonstrations (ablation) | CoT · GSM8K | accuracy: 68.5 -> 70.3 | No clear effect |
| Add incorrect EoT paths as in-context demonstrations (ablation) | CoT · GSM8K | accuracy: 68.5 -> 69.2 | No clear effect |
| Add correct EoT paths as in-context demonstrations (ablation) | CoT · GSM8K | accuracy: 68.5 -> 73.2 | Helped |
| Use EoT structural embeddings with BFS | Language agents · MATH | accuracy: 34.6 -> 36.7 | Helped |
| Use EoT structural embeddings with MCTS | Language agents · MATH | accuracy: 32.1 -> 37.4 | Helped |
Surprising findings
- Textual graph descriptions did not improve over vanilla prompts and often reduced efficiency, as repeated action nodes lengthen context.
- Prompt-tuning was competitive with EoT when paired with MCTS, unlike BFS where EoT was clearly better.
Limitations
- Blockworlds training data is small (100 instances), limiting generalization claims.
- Performance gains on some Qwen settings and steps are small or negative (e.g., Qwen 4-step EoT-MCTS -1.7%).
Experimental setup
Datasets: GSM8K Blockworlds MATH
Benchmarks: GSM8K MATH Blockworlds
Metrics: solve rate accuracy
Baselines: CoT Self-Refine ToT-BFS RAP-MCTS Prompt-tuning Textual graph
Builds on: Tree of Thoughts Reasoning via Planning Graph Transformer Prompt tuning
Closest papers by meaning
- Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models (ICML 2024 · similarity 0.88)
- Eliciting Reasoning in Language Models with Cognitive Tools (NeurIPS 2025 · similarity 0.88)
- Markovian Transformers for Informative Language Modeling (ICLR 2026 · similarity 0.87)
- Non-myopic Generation of Language Models for Reasoning and Planning (ICLR 2025 · similarity 0.87)
- Graph-enhanced Large Language Models in Asynchronous Plan Reasoning (ICML 2024 · similarity 0.87)
- CodePlan: Unlocking Reasoning Potential in Large Language Models by Scaling Code-form Planning (ICLR 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.