Can LLMs Compress (and Decompress)? Evaluating Code Understanding and Execution via Invertibility

AI summary

Overview

Research area: Code LLM evaluation, program execution reasoning, and self-consistency benchmarks.

Technical level: Intermediate — the paper is readable for anyone familiar with LLMs and basic algorithms, though the four compression algorithms and the invertibility framing require some careful reading.

Scope: The paper introduces RTCE, a benchmark that tests whether Code-LLMs can perform a round-trip through lossless compression algorithms — encoding an input and then decoding it back exactly — and shows that models can pass each direction separately while failing the combined loop.

What This Paper Is About

Existing code benchmarks score forward execution (given input and code, predict the output) and backward execution (given output and code, predict the input) independently. That leaves a blind spot: a model can appear correct in both directions using pattern matching while holding internally contradictory representations of the algorithm.

This paper argues that genuine code understanding requires invertibility — the ability to apply a transformation and its exact inverse so the original data is recovered bit-for-bit. The authors build a benchmark around lossless compression (LZW, Arithmetic Encoding, RLE, Huffman) where the round-trip must be exact, not merely semantically equivalent, and use it to probe whether current LLMs have coherent bidirectional reasoning.

Key Contributions

1. RTCE (RoundTripCodeEval), a new benchmark for code invertibility: 250 inputs across four diverse data families, each evaluated on four code execution tasks (forward encode, forward decode, and the two inverse variants), yielding 1,000 evaluation examples with deterministic, execution-free exact-match ground truth.

2. A formal framing of code understanding as a bijection fidelity problem, distinguishing it from prior round-trip work (IdentityChain, Round-Trip Correctness) that only requires semantic equivalence between code and natural-language descriptions rather than exact data identity.

3. A three-paradigm evaluation covering 15 LLMs across 1B–33B parameters under zero-shot prompting, iterative self-reflection with structured critique and revision, and supervised fine-tuning on filtered execution traces translated into natural-language reasoning.

4. Diagnostic findings invisible to single-direction benchmarks, including the encoding–decoding asymmetry, the "Huffman paradox" (all models at 0% encoding but nonzero decoding), and evidence that tokenization is not the bottleneck.

Main Findings

• Round-trip consistency fails across the board. Every model and every intervention yields only modest gains; none closes the gap. Models frequently pass individual forward and backward tasks yet fail the combined round-trip, exposing mutually inconsistent internal representations.

• A consistent task-difficulty hierarchy emerges: Output Prediction (x → z) > Output Prediction with Inversion (x → z via inverted decoder) > Input Prediction (z → x′) > Input Prediction with Inversion (z → x′ via inverted encoder). Inverse variants that combine strict output demands with inverted logic are hardest.

• Scale helps, but unevenly by algorithm. Models at or below 3.8B score near zero everywhere. The 7–9B range generalizes only on RLE. Above 14B, RLE and LZW improve substantially. Huffman encoding remains unsolved by all 15 models, scoring 0% exact match.

• The Huffman paradox. All models score 0% on Huffman encoding, yet QwQ-32B reaches 7.9% on Huffman decoding and 11.1% on decoding with inversion. Decoding is a tree traversal over a provided tree; encoding requires building the frequency table, constructing the tree, and emitting variable-length codes — a multi-stage hierarchical procedure no model handles.

• Encoding–decoding asymmetry. Decoding often outperforms encoding because the model can exploit surface regularities in the encoded string. Arithmetic Encoding is the exception: QwQ-32B scores 27.6% on AE encoding but only 2.3% on AE decoding, a 12x collapse, because decoding demands numerically fragile inverse floating-point interval arithmetic.

• Self-reflection saturates immediately. Multi-turn critique-and-revision helps on the first round, especially for inversion tasks suffering from shallow errors, but plateaus sharply afterward. Unaided self-critique cannot repair systematic state-tracking errors or incorrect inversion logic.

• Reasoning-distilled models outperform general and code-specialist models of comparable size. DeepSeek-R1-Distill-Qwen-14B beats similarly sized general-instruction and code models, suggesting chain-of-thought pretraining aids structured multi-step simulation.

• Tokenization is not the root cause. Llama and Qwen use fundamentally different tokenization regimes yet both fail consistently. More decisively, QwQ-32B and Qwen2.5-Coder-32B share identical tokenizers and parameter counts, but QwQ scores 1.86x higher on AE — attributable to reasoning-focused training.

• Edit Similarity stays above zero even at 0% exact match, showing models produce plausible but symbol-imprecise outputs. The benchmark genuinely demands exact fidelity.

• Algorithmic complexity is not the sole cause of failure. Even RLE, the simplest bijection tested, is not solved.

Methodology in Plain English

The researchers picked four well-understood lossless compression algorithms that each represent a distinct design paradigm: RLE (run aggregation), LZW (dictionary-based), Arithmetic Encoding (statistical interval coding), and Huffman (prefix coding). These are deterministic, have unique correct outputs, and require genuine multi-step bookkeeping rather than pattern matching.

They generated 250 test inputs from four realistic data families: patterned strings, Apache-style structured logs, YAML-like configuration files (Kubernetes, Docker Compose, Terraform), and small CSV/TSV tables. Reference implementations produce exact ground-truth outputs under a fixed seed, so scoring is a simple exact-match check with no execution or hidden unit tests.

Each input is tested on four tasks that together form a closed loop: apply the encoder, invert the encoder, apply the decoder, and invert the decoder. A model is only truly consistent if the full chain reconstructs the original input exactly.

To see if the capability can be instilled rather than merely measured, they also ran two interventions. First, an iterative self-reflection loop where the model critiques its own draft, issues a KEEP or REVISE verdict, and edits accordingly without seeing the ground truth. Second, supervised fine-tuning: they instrumented reference solutions with a tracing decorator, captured step-by-step variable values from stderr under a strict timeout, filtered traces for clean completions, translated them into natural-language reasoning steps using Qwen3-32B, and fine-tuned with LoRA.

Scoring uses three metrics: Exact Match, Edit Similarity for partial credit, and Pass@5 to measure the sampling ceiling independent of single-shot reliability.

Why This Matters

Impact on research. The paper reframes code understanding as a coherence problem rather than a correctness problem. By showing that isolated forward accuracy is a weak proxy for mechanistic reasoning, it challenges the field's reliance on single-direction benchmarks and demonstrates that failures previously attributed to scale or tokenization are actually failures of logical reasoning. The finding that self-critique saturates after one round is a concrete data point against unaided self-improvement loops.

Real-world applications:

• Code assistants and refactoring tools — round-trip consistency is exactly what you need before trusting an LLM to rewrite serialization, encryption, or data transformation code, where reversibility is non-negotiable.

• Data pipeline engineering — compression, encoding, and format conversion routines are ubiquitous in ETL; a model that cannot invert them cannot be safely delegated to maintain them.

• Verification and testing — round-trip invariants are a cheap, deterministic oracle. This work shows they can be repurposed as an evaluation signal for model capability on high-stakes code.

• Model selection for structured tasks — the paper's hierarchy shows reasoning-distilled models justify their cost on multi-step symbolic work, while general instruction models fail even on trivial bijections.

Industry relevance. Teams deploying LLMs for code generation, data engineering, or legacy system migration should treat round-trip verification as a gating check. The paper provides evidence that a model passing your forward tests may still hold a broken internal model of the algorithm.

Future Directions

1. Extending round-trips to arbitrary chain length. The authors note the current pipeline is a chain of length 1 but could be extended to longer compositions, which would test whether errors compound predictably or interact nonlinearly.

2. Grounding self-correction in execution feedback. The saturation result implies self-critique alone is insufficient; combining it with actual interpreter or compiler feedback (as suggested by Olausson et al.) is the natural next step.

3. Scaling fine-tuning beyond trace supervision. SFT on execution traces yielded only modest gains. Whether larger curated datasets, reinforcement learning from execution outcomes, or process reward models can close the gap remains open.

4. Understanding the Huffman gap and AE asymmetry. Why encoding is universally harder than decoding, and why hierarchical tree construction is so resistant to current architectures, are unanswered mechanistic questions worth targeted interpretability work.

Target Audience

This paper is most valuable for LLM evaluation researchers, benchmark designers, and interpretability researchers interested in code reasoning. It also serves practitioners building code assistants or automated data-engineering tools who need to know the limits of current models on reversible transformations. Graduate students and advanced undergraduates working on program synthesis or execution reasoning will find the problem formalization and the four-task decomposition directly reusable.

Authors’ abstract

LLMs demonstrate strong performance on code benchmarks, yet consistent reasoning across forward and backward execution remains elusive. We present RoundTripCodeEval (RTCE), a benchmark of four code execution reasoning tasks that evaluates round-trip consistency through execution-free, exact-match assessment of bijection fidelity across four lossless compression algorithms. We evaluate state-of-the-art Code-LLMs under zero-shot prompting, supervised fine-tuning on execution traces, and iterative self-reflection. All approaches yield only modest improvements and none closes the gap, revealing that current LLMs lack the internal coherence required for reliable bidirectional code reasoning. RTCE surfaces findings invisible to existing benchmarks: models frequently pass individual forward and backward tasks yet fail the combined round-trip, exposing mutually inconsistent internal representations; SFT and self-reflection saturate after one revision round, indicating they cannot repair fundamental algorithmic misunderstandings; and failures persist even on simple bijections such as RLE, suggesting that algorithmic complexity is not the sole root cause.\footnote{Code and dataset are available at https://github.com/Nickil21/round-trip-code-compression.