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

作者Nickil Maveli, Antonio Vergari, Shay B. Cohen

机构School of Informatics, University of Edinburgh

链接arxiv.org/abs/2601.13398

基准RoundTripCodeEval (RTCE) — 250 输入 × 4 任务 = 1,000 样例

通过让 LLM 同时执行压缩编码与逆向解码，揭示现有模型缺乏真正双向代码推理一致性的深层问题。

图 1：标准无损压缩管道——输入 X 经 enc 压缩为 z，再经 dec 还原为 X′。RTCE 基准正是在这条管道上设计四类推理任务。

研究动机

问题难在哪：现有 code benchmark 几乎只测单向执行（给代码预测输出，或给输出反推输入），无法评估模型是否真正理解算法的双向语义一致性。一个靠模板匹配做到"正向预测"的模型，遇到逆向任务就会暴露破绽。
现有方法的问题：
- HumanEval / MBPP 等只测代码生成，不测执行推理；
- CRUXEval 测输入/输出预测但方向单一；
- 无基准要求模型同时在正向与逆向任务上保持自洽（round-trip consistency）。
核心 insight：无损压缩算法天然是双射（bijection）——enc 与 dec 互为逆函数，因此可以严格验证 \(\forall x \in \mathcal{X},\ \text{dec}(\text{enc}(x)) = x\)，把"能否真正执行代码"转化为可量化的 round-trip 测试。

核心方法

1. 四类推理任务

RTCE 将一条压缩管道拆成四个方向，要求 LLM 分别扮演"执行正向/逆向函数"的角色：

图 2：四类任务示意。蓝色为正向函数，橙色为逆向函数；箭头方向对应模型需要心算执行的函数。

#	任务名	给定	预测	难点
1	Output Prediction	x, enc	\(\hat{z}\)	正向执行 enc
2	Input Prediction with Inversion	z, enc	\(\hat{x}'\)	心算 enc⁻¹
3	Output Prediction with Inversion	x, dec	\(\hat{z}\)	心算 dec⁻¹
4	Input Prediction	z, dec	\(\hat{x}'\)	正向执行 dec

Round-trip check：任务 1+4（或 2+3）的输出串联后，若 \(x = x'\) 则模型自洽。

RLE 具体示例（输入 x = "AAABBBCC"，z = [(A,3),(B,3),(C,2)]）

任务 1 — Output Prediction（正向执行 enc）

给定：x = "AAABBBCC"，以及 RLE 编码器代码
预测：ẑ = ?

正确答案：ẑ = [(A,3),(B,3),(C,2)]
要求：LLM 心算逐字符扫描，统计连续重复段，输出 (字符, 计数) 列表

任务 2 — Input Prediction with Inversion（心算 enc⁻¹）

给定：z = [(A,3),(B,3),(C,2)]，以及 RLE 编码器代码（注意：不是解码器！）
预测：x̂' = ?

正确答案：x̂' = "AAABBBCC"
要求：LLM 必须先在脑中推导出 enc 的逆函数（即 dec），再执行它

任务 3 — Output Prediction with Inversion（心算 dec⁻¹）

给定：x = "AAABBBCC"，以及 RLE 解码器代码（注意：不是编码器！）
预测：ẑ = ?

正确答案：ẑ = [(A,3),(B,3),(C,2)]
要求：LLM 必须先在脑中推导出 dec 的逆函数（即 enc），再执行它

任务 4 — Input Prediction（正向执行 dec）

给定：z = [(A,3),(B,3),(C,2)]，以及 RLE 解码器代码
预测：x̂' = ?

正确答案：x̂' = "AAABBBCC"
要求：LLM 展开每个 (字符, 计数) 对，拼接输出字符串

任务 2 和 3 是"逆向"任务——提供的是另一方向的函数代码，模型须自行推导逆函数后再执行，难度显著高于任务 1 和 4。

2. 四种压缩算法

选取了四种难度递增的无损压缩算法，覆盖字典型、统计型、行程型、前缀码型：

RLE（行程编码）
最简单；重复模式识别。输出为 (符号, 计数) 元组。

LZW（字典编码）
字典随输入动态增长，产生整数序列。状态追踪难度高。

Arithmetic Encoding (AE)
统计区间编码，输出浮点数。极小的算术误差即导致失配。

Huffman Coding
最难；需构建频率表 + 前缀树，输出比特串。

3. 数据集构成

250 个唯一输入来自约 45 个类别（有规律字符串、结构化日志、YAML 配置、表格数据），长度从几字符到数百字符不等，覆盖短/中/长三个区间，确保难度分布均衡。

4. 评估指标

Exact Match (EM)：最严格，要求完全匹配。
Edit Similarity (ES)：归一化 Levenshtein 距离，捕获部分正确。
Pass@5：5 次采样中至少 1 次命中的概率。

5. 三种实验范式

依次评估三条改进路径，测试是否有方法能突破 LLM 的 round-trip 瓶颈：

Zero-shot prompting：直接推理，无额外训练。
Self-reflection（多轮修订）：模型先生成答案，再批判自身输出并修订。
Supervised fine-tuning（SFT）：用执行轨迹对 QwQ-32B 做 LoRA 微调。

6. 最关键的一句话

要通过 round-trip 测试，模型必须同时维护精确的内部状态并执行逆向推理，这远比"正向代码生成"更能暴露模型是否真正理解算法。

主要实验结果

24测试模型数

1,000总评估样例

4压缩算法

≈0%Huffman Pass@5（多数模型）

RQ1：Zero-Shot 性能

所有模型的任务难度排序一致：Output Prediction ≫ Output Prediction-Inversion ≫ Input Prediction ≫ Input Prediction-Inversion。规模效应明显：

≤3.8B 参数：几乎全面失败；
7–9B：能处理 RLE 等重复模式；
≥14B：RLE 和 LZW 有一定成功率，但 Huffman 对所有模型几乎为零。

RLE radial — 图 11：RLE 的 Pass@5 雷达图——最易算法，推理型大模型（QwQ-32B, DeepSeek-R1）多边形最大且最对称。

Huffman radial — 图 12：Huffman 的 Pass@5 雷达图——几乎所有模型在所有轴上坍缩为零。

RQ2：Self-Reflection（多轮修订）

图 3：AE 算法的多轮修订结果。逆向任务初始精度低但第一轮提升明显；第二轮后收益递减，模型进入"自我修订饱和"。

结论：自我反思能带来增量改善，但无法突破算法理解层面的根本性错误——模型达到自洽上限后便停滞。

RQ3：Fine-Tuning（SFT）

对 QwQ-32B 使用 LoRA 在执行轨迹上微调后，Pass@5 提升幅度约 30–87%（因算法和任务而异），但模型仍无法同时在四类任务上保持双向一致。对分布内模式的过拟合不能保证泛化到新输入。

输入长度的影响

所有算法的 Pass@5 均随输入长度增加而下降，但下降速度不同：

RLE：下降最缓，对长输入最鲁棒；
AE：超过 100 字符后几乎归零；
LZW：字典膨胀使长输入指数级变难；
Huffman：所有长度下均接近零——困难来自算法复杂度而非输入长度。

算法难度总结

难度（从易到难）：RLE < LZW ≈ AE << Huffman

- RLE：局部重复识别，状态最简
- LZW：字典状态需精确追踪
- AE：浮点精度敏感，极小误差致失配
- Huffman：频率表 + 树构建 + 比特级操作，最高层次推理

典型失败模式

展开：三类主要失败模式

模板匹配退化：模型在正向任务上看似成功，实为记忆了常见输出模式，遇到逆向任务立即失败。
算术 / 记账错误：编码需维护精确演化的内部状态（字典、区间），即使微小错误也会使 EM 归零。
层次推理缺失：Huffman 需要从频率 → 树 → 前缀码 → 比特串的多层推理链；模型在中间层断裂。

局限与展望

模型覆盖：主要评估开源模型，GPT-4o / Claude 等闭源模型评估有限，结论是否普适存疑。
语言单一：仅评估 Python 实现；其他语言（C++、Rust）的表现未知。
范式局限：压缩-解压框架未覆盖其他可逆性形式（代码重构的等价性、反编译、程序合成）。
静态评估：无法捕获运行时现象——副作用、并发、外部 I/O 依赖。
研究趋势：该工作指出，提升 LLM 代码推理可靠性的关键在于内部语义一致性，而非单纯扩大规模或增加微调数据。未来可探索：显式程序状态追踪、可验证推理链（如 chain-of-thought with symbolic verifier）、以及将 round-trip 一致性作为 RLHF 奖励信号的训练范式。