cs.AISep 18, 2026

The Communication Bottleneck: A Round-Trip Study of Tree-Structured Expression Serialization in Language Models

Authors: Xavier Suau, Alex Ferrando de las Morenas, Luca Zappella, Samy Bengio

Organizations: Apple

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

When language models reason in chain-of-thought or exchange free-text intermediates, they serialize structured information into natural language. How much tree-structured compositional content survives this bottleneck? We propose a round-trip protocol that answers this question empirically for tree-structured expressions. A generator converts a procedurally generated arithmetic expression into a word problem, a separate extractor recovers the expression from the word problem alone, and symbolic equivalence provides an exact oracle. Evaluating all pairwise combinations of sixteen models yields a communication matrix whose marginals separate generation quality from extraction quality. Three main findings emerge. First, the channel is lossy and asymmetric: swapping which model generates and which extracts shifts accuracy by up to 60.4 points, and the best pair reaches 92.9% by combining different models on each end rather than the same model on both. Second, at least 73.6% of round-trip failures originate at generation, and difficulty is driven by tree structure (operator count, depth, right-branching) rather than model family. Third, the channel is trainable: ~3600 fine-tuning examples that share the evaluation's operators and tree shapes lift every open-weight model above untrained Gemini-3.1-Pro, an upper bound under matched semantics. A disjoint-domain regime with new operators and vocabulary also raises every open-weight model, confirming the gain is not an artifact of matched semantics, though a gap to the frontier remains. Together these results identify tree-structured expression serialization as a primary limiting factor when models communicate hierarchical structure through natural language.

Explore similar work

CardsList
Sep 22, 2026cs.CL

Capable yet Parsimonious: Extracting and Characterizing Hidden Chain-of-Thought in Frontier Models

The rapid capability gains of frontier language models are widely attributed to improved reasoning abilities, yet this cannot be verified as raw CoT traces in closed-source systems are hidden. By registering a simple custom tool through a standard API feature, we induce frontier models to externalize intermediate reasoning. Because these traces may reflect post-hoc rationalization rather than genuine reasoning, we first evaluate against native CoT on open-source models and extend to closed-source frontier models including GPT-6 Astra. We find that the extracted reasoning matches native reasoning performance and substantially outperforms no-reasoning baselines, across competition mathematics, science, and code generation. We then characterize how frontier models structure their intermediate reasoning. Across token efficiency, reasoning-step types, and induced reasoning trees, we identify systematic differences in how models externalize, compress, and organize reasoning. We find that Astra exhibits token-efficient directed reasoning, selecting a correct trajectory earlier, while resolving elementary steps internally and externalizing only crucial reasoning. These findings provide a behavioral lens on frontier-model reasoning beyond benchmark scores.
Xiaoyu Luo, Tao Ren, Wenrui Yu +3
Topic pending
AskPDF
Jun 9, 2026cs.LG

Express Language Modeling

We introduce a new tool, Express, for converting a non-causal attention approximation into a causal approximation with matching approximation guarantees. When combined with the state-of-the-art Thinformer approximation, Express improves upon the best known causal attention guarantees, delivering log⁡3/2(n)/s\log^{3/2}(n)/s approximation error with only O(s)O(s) memory and O(s2log⁡2(n))O(s^2 \log^2(n)) compression overhead for a sequence of length nn. We pair these developments with an efficient I/O-aware Triton implementation, demonstrate substantial speedups over FlashAttention 2, and use Express to overcome four resource bottlenecks in the language modeling pipeline: long-context prefill, KV cache compression, long-form memory-constrained decoding, and long-form compute-constrained decoding.
Albert Gong, Annabelle Michael Carrell, Raaz Dwivedi +1
Graph Language ModelsCausal AttentionExpressivity
AskPDF
Jun 8, 2026cs.AI

Capacity, Not Format: Rethinking Structured Reasoning Failures

Prior work treats structured output as a reasoning tax, but this framing is incomplete: the cost of formatting depends strongly on a model's spare capacity. Using information-matched prose controls and a four-level schema complexity gradient, we separate format-specific effects from prompt-length confounds across 4 models and 5 benchmarks with 0% parse failures on successfully generated responses. We find that structured formats are capacity-dependent. Models with sufficient headroom absorb JSON constraints without degradation (Sonnet: 88.7±4.088.7\pm4.0% JSON vs. 89.3±1.789.3\pm1.7% CoT on MATH-Hard). In contrast, formats severely degrade models operating near their limits through two distinct mechanisms. First, under standard token budgets, Haiku drops 36.2pp (p<0.0001p < 0.0001) largely due to truncation. Second, even with extended budgets eliminating truncation, GPT-4o-mini drops 28.0pp (p<0.001p < 0.001), revealing pure capacity competition independent of token exhaustion. This format penalty scales with schema complexity (McNemar p<0.0001p < 0.0001) and cannot be explained by prompt length alone. Furthermore, these results qualify claims of frontier model immunity: on AIME competition math, Opus 4.7 drops from 96.2% to 91.0% under JSON (−5.3-5.3pp; the displayed percentages are independently rounded, exact difference is 7/133=5.267/133 = 5.26pp ≈5.3\approx 5.3pp). A delayed-structure ablation -- reasoning freely before formatting -- recovers most of the lost accuracy (3-run mean: 80--87%), supporting the capacity competition mechanism. The practical implication is not to avoid structured output, but to match it to capacity: when a model is near its limits, think first, format later.
Hengxin Fan
Reasoning FailuresCapacityFrontier ModelsLatent Confounders
AskPDF