Research map / Large language models / Agents, code and math
Guess & Sketch: Language Model Guided Transpilation
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 Guess & Sketch, a neurosymbolic assembly-to-assembly transpiler (ARMv8 <-> RISC-V) where an LM supplies candidate translations, attention-based alignments and low-confidence flags, and a Rosette SMT-based solver repairs flagged basic blocks.
Problem
Automatically translating assembly code between ISAs (ARMv8 and RISC-V) is hard: rule-based transpilers are hand-engineered and don't scale to new ISAs, symbolic synthesis scales poorly beyond a few lines, and pure LMs lack guaranteed correctness.
Approach
Extract sequence-level alignment (from cross-/self-attention) and token-level confidence from a trained LM, mark potentially erroneous pure basic blocks, and pass those aligned input/output subsequences as sketches with specifications to a symbolic solver (Rosette) that fills holes so output is semantically equivalent; falls back to the LM output if no solution.
Key results
- On RISC-V to ARMv8 Project Euler, Guess & Sketch reaches 80% vs 11.1% for few-shot GPT-4 and 68.9% for the Encoder-Decoder baseline; ARMv8 to RISC-V Project Euler reaches 75.6% vs 24.4% for the engineered transpiler.
- Across three test sets and both directions, the method is reported to transpile 57.6% more examples than GPT-4 and 39.6% more than the engineered transpiler, and 13.2% more than the best baseline.
- On 82 additional Project Euler programs, Guess & Sketch gains roughly 10 points over the Encoder-Decoder (41.5% vs 34.1% and 51.2% vs 37.8%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add symbolic sketch solving guided by language-model alignments and confidence | Encoder-Decoder · Project Euler, RISC-V to ARMv8 | full program accuracy: 68.9% -> 80% | Helped |
| add symbolic sketch solving guided by language-model alignments and confidence | Encoder-Decoder · Benchmarks, RISC-V to ARMv8 | full program accuracy: 6.3% -> 18.8% | Helped |
| add symbolic sketch solving guided by language-model alignments and confidence | Encoder-Decoder · Unix Commands, RISC-V to ARMv8 | full program accuracy: 36.4% -> 81.2% | Helped |
| add symbolic sketch solving guided by language-model alignments and confidence | Encoder-Decoder · Project Euler, ARMv8 to RISC-V | full program accuracy: 66.7% -> 75.6% | Helped |
| add symbolic sketch solving guided by language-model alignments and confidence | Encoder-Decoder · Benchmarks, ARMv8 to RISC-V | full program accuracy: 6.25% -> 25.0% | Helped |
| add symbolic sketch solving guided by language-model alignments and confidence | Encoder-Decoder · Unix Commands, ARMv8 to RISC-V | full program accuracy: 81.2% -> 81.2% | No clear effect |
| add symbolic sketch solving guided by language-model alignments and confidence | Encoder-Decoder · Project Euler, RISC-V to ARMv8 (additional problems) | full program accuracy: 34.1% -> 41.5% | Helped |
| add symbolic sketch solving guided by language-model alignments and confidence | Encoder-Decoder · Project Euler, ARMv8 to RISC-V (additional problems) | full program accuracy: 37.8% -> 51.2% | Helped |
| add symbolic sketch solving guided by language-model alignments and confidence | Encoder-Decoder · Project Euler, RISC-V to ARMv8 | average number of samples: 30.1 -> 21.3 | Helped |
| add symbolic sketch solving guided by language-model alignments and confidence | Encoder-Decoder · Project Euler, ARMv8 to RISC-V | average number of samples: 34.3 -> 25.3 | Helped |
| vary confidence threshold gamma from 0.8 to 0.95 (ablation) | Guess & Sketch · Project Euler | number of corrected programs | No clear effect |
| increase confidence threshold gamma from 0.8 to 0.95 (ablation) | Guess & Sketch · Project Euler | inference runtime: 2.2x | Hurt |
Surprising findings
- Fine-tuned pre-trained code LLMs (StarCoder, CodeLlama) performed much worse than a small from-scratch BART-style encoder-decoder trained on the same paired data.
- Few-shot GPT-4 mostly fails due to invalid ISA instructions rather than semantic errors.
Limitations
- Sketch correction depends on the alignment from the LM; poor alignment limits repairs.
- Memory and stack management are hard for the solver and are excluded from pure basic blocks.
- Equivalence is checked only on a small finite set of inputs, with no formal proof; length limited by context window.
Experimental setup
Datasets: The Stack (C files compiled to ARMv8 and RISC-V assembly pairs) Project Euler C implementations Benchmarks Game C implementations Basic Unix Commands C implementations Additional 82 Project Euler C problems
Benchmarks: Project Euler Benchmarks Game Unix Commands
Metrics: full program accuracy (execution output match) average samples used
Baselines: Few-shot GPT-4 Engineered ARMv8-to-RISC-V transpiler (IBM Haifa arm2riscv) FT StarCoder FT CodeLLaMA Encoder-Decoder
Builds on: BART Rosette Sketching (program synthesis) LoRA Transcoder
Closest papers by meaning
- QiMeng-NeuComBack: Self-Evolving Translation from IR to Assembly Code (NeurIPS 2025 · similarity 0.89)
- Automatically Testing Functional Properties of Code Translation Models (AAAI 2024 · similarity 0.86)
- LILO: Learning Interpretable Libraries by Compressing and Documenting Code (ICLR 2024 · similarity 0.86)
- Unsupervised Evaluation of Code LLMs with Round-Trip Correctness (ICML 2024 · similarity 0.85)
- Nova: Generative Language Models for Assembly Code with Hierarchical Attention and Contrastive Learning (ICLR 2025 · similarity 0.85)
- SelfCodeAlign: Self-Alignment for Code Generation (NeurIPS 2024 · similarity 0.85)
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.