acceptodds
Under review as a conference paper at ICLR 2027

Smoothing Does Not Compress & Hard Structured Inference

Abstract

Differentiable structured-inference layers replace hard recurrences by regularized operators. We ask whether this smoothing can reduce the representation cost of the underlying hard value function. For a broad class of finite DAGs, the answer is no in the sublinear-ray regime. We pair a finite-temperature computation with a same-wiring tropical shadow: bounded min/max deformations are replaced by hard extrema, positive scalar gates are retained, and finite constants are removed. A recursive DAG budget then bounds the discrepancy on every score ray. Consequently, any -accurate realization has the target's exact shadow and inherits its min-plus or STC lower bound without a size loss. The same budget gives finite-scale open-cone slope and relative-support floor certificates, while annealing changes only the deformation term. For -ary linear-code inference, we prove ; for the grid cycle code, , giving a barrier. CUDA double-precision experiments recover the exact width threshold and code-distance slopes, and separate deformation from representation error under annealing. Signed affine preprocessing is covered by a signed shadow with an explicit affine budget.

Primary area:
learning theory
Keywords:
smoothed inference, structured inference, differentiate dynamic programming, tropical circuits, representation lower bounds

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_hDUuOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper solve the problem that If the hard min/max operations in dynamic programming are replaced with differentiable softmin/softmax, can the originally complex structured inference be implemented using smaller neural networks or computational circuits? They prove the conclusion via proof and experiments.

Critical strengths

The conclusion of this paper is important. I like the proof structure. The paper is relatively easy to follow.

Critical weaknesses

The main lower bound transfer theorem requires that the approximation error of the smooth network is sublinear along every fractional ray. However, the corollary establishing the exponential lower bound for the regularized linear-code inference layer does not restate this critical approximation condition in its statement. Without this condition, the claimed lower bound does not hold for circuits arbitrarily constructed from admissible operators. The authors should explicitly state the assumptions within this corollary, and carefully distinguish the exact lower bound for pure min-plus circuits from its transfer to approximate, smooth implementations.

Experiments are primarily conducted on synthetic linear codes and truncated trellis architectures. It is difficult to assess the extent to which the conclusions characterize more general learnable DAG architectures or real-world structured prediction tasks. The authors should clarify whether the reported quantity is the global supremum or the empirical maximum over sampled inputs, and provide stronger validation beyond fixed trellis truncation.

Questions for authors

See Weakness.

Reviewer_LVpROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies whether replacing min operations in hard structured inference with differentiable smoothing operators such as softmin can reduce the network size required to accurately represent the optimal cost function. Using the bounded deviation between smooth and hard operators, it proposes an analytical framework combining a tropical shadow with a recursive error budget over the computation graph. This framework maps a smooth network to a hard min-plus network with the same wiring and proves that, if the approximation error must be o(t) when inputs are scaled by a factor of t along every admissible direction, the smooth network must inherit the size lower bounds of the hard network. When the network is too small, the error grows linearly with t over a nonempty region of input directions. Experiments show that, in a pruned trellis for the 5×5 grid cycle code, representation error can be eliminated only by restoring the full width of 16 states. Although lowering the temperature reduces smoothing error by 96.8%, it does not change the asymptotic error caused by missing states. Overall, the paper provides a framework for analyzing size lower bounds and error certificates, showing that under the operator model and accuracy requirements studied, smoothing can improve differentiability but cannot compensate for insufficient representational capacity.

Critical strengths
  1. The analysis provides a fairly complete chain of evidence: from bounded deviations of local operators to a graph-wide error budget, then to the exactness of the asymptotic shadow, the transfer of size lower bounds, and concrete instances, followed by experiments testing the corresponding error mechanisms. The experiments support these theoretical predictions rather than a universal conclusion about the compressibility of arbitrary neural networks.
  2. Quantitative error guarantees are provided at finite scales. Beyond proving that undersized smooth networks cannot achieve sublinear approximation error, the recursive error budget establishes an explicit relationship among input scale, the hard-shadow gap, and total error, showing when insufficient representational capacity manifests as unavoidable linear error.
Critical weaknesses
  1. The condition requires the error to be o(t) after inputs are scaled by t along every admissible input direction. This condition does not directly answer whether a smaller smooth network can achieve sufficiently good average accuracy over a fixed, bounded input range or a particular data distribution.
  2. The experimental exploration of compression strategies is narrow. The experiments mainly prune a fixed trellis, and training optimizes only temperatures and constants that do not change the hard shadow. The results therefore primarily validate the specified error mechanisms, without examining capacity–accuracy trade-offs under alternative wiring at the same budget, learnable structures, or data-aware compression.
Questions for authors
  1. Could you check the formatting on page 9? The allocation of space is unbalanced: page 9 still has unused space, while key experimental settings and most of the full results are left in the appendix.
  2. Within a fixed input range, please compare the test errors of hard and smooth networks at different budgets and sweep the input scale to determine whether smoothing can improve the accuracy of small networks at finite scales and when any such advantage disappears.
  3. In addition to the existing trellis pruning based on codeword flow, please include random pruning, data-aware pruning, or alternative wiring schemes. Under a matched gate-count budget, report total error, smoothing error, and the shadow gap separately to distinguish which phenomena depend on the pruning strategy.
  4. Could you clarify that “representation cost” refers to circuit size and discuss how it differs from neural parameter count and sample complexity?
Reviewer_crnuOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper investigates whether smoothing hard minimum/maximum operations in differentiable structured inference can reduce the computational complexity required to represent the underlying optimization problem. It introduces a tropical shadow construction and proves that bounded smoothing preserves exact circuit-size lower bounds under sublinear approximation error along score rays. For linear-code inference, the authors derive exponential lower bounds for certain code families, including grid cycle codes. Experiments on synthetic coding-theory instances validate the predicted representation barriers and show that smoothing and learned annealing reduce approximation error without overcoming limitations imposed by the circuit structure.

Critical strengths

Theoretical contributions with formal guarantees

The paper establishes a general connection between differentiable approximations of hard inference operations and their underlying circuit complexity. In particular, transferring exact representation lower bounds to bounded smoothing architectures, including arbitrary DAG sharing, provides a potentially valuable theoretical insight into the limitations of differentiable structured inference.

Careful experimental verification of theoretical predictions

The experiments investigate representation complexity across several coding-theory instances and validate the predicted width thresholds and approximation-error behavior. The additional experiments on smoothing temperatures and learned annealing support the theoretical distinction between approximation errors introduced by smoothing and fundamental limitations of the underlying computational structure.

Critical weaknesses

Insufficient motivation and difficult presentation

The paper is extremely difficult to follow without substantial prior knowledge of tropical circuit complexity and coding theory. It introduces mathematical definitions and technical results almost immediately, without first explaining the underlying problem through an intuitive example or motivating why the representation complexity of differentiable structured inference matters in practice. Important concepts and assumptions are introduced with little explanation, making the contributions difficult to assess for a general ICLR audience. More importantly, the paper does not sufficiently explain what its theoretical results imply for practical machine-learning architectures or why these representation barriers are relevant beyond the considered theoretical setting.

Limited applicability and experimental validation of the theoretical results

The strongest lower bounds apply to a restricted computational model involving addition and bounded deformations of min/max operations, with approximation guarantees requiring sublinear error along unbounded score rays. It remains unclear how these results extend to practical neural architectures with general affine transformations, nonlinearities, and learned representations, or to approximation on bounded input distributions. Furthermore, the experiments primarily validate the expected behavior of truncated trellis architectures rather than investigating alternative computational structures or learned compression methods. The theoretical presentation also contains an apparent error in the proof of Theorem 11, where the stated numerical lower-bound constants do not follow from the provided inequalities. Although likely fixable, this raises concerns about the precision of the theoretical arguments.

Questions for authors

1. Motivation and practical relevance (clarification).

Could the authors provide a more intuitive motivation for the investigated problem, ideally through a concrete example of differentiable structured inference? In particular, which practical ML architectures fall within the considered computational model, and what implications do the derived lower bounds have for their design? Since general signed-affine networks and learned representations are not covered by the strongest lower bounds, it remains unclear how broadly the conclusions apply.

2. Novelty and theoretical soundness (clarification).

How do the derived linear-code complexity bounds differ from existing results on trellis state complexity and tropical circuit lower bounds, particularly the recent work on tropical factorization ranks for linear codes? Additionally, could the authors clarify the proof of Theorem 11? The numerical constants in Appendix A appear inconsistent with the preceding inequalities, which seem to establish weaker lower bounds than those stated.

3. Significance of experimental validation (clarification and additional evidence).

The experiments primarily investigate truncated trellis architectures, where reducing the number of retained states naturally introduces representation errors. To what extent do these results support the more general claims about arbitrary DAG architectures? In particular, the observed threshold of 16 trellis states should be distinguished from the theoretical lower bound on circuit size. Could the authors clarify this relationship and provide evidence or examples showing that the derived bounds meaningfully constrain alternative differentiable inference architectures rather than only the particular trellis truncation considered?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.