source/tex/src/motivation.tex

\section{Mutual Information Analysis of Table Data}
\label{sec:motivation}
Table data is widely used in real-world applications, yet its structural properties for LLM training remain underexplored. Unlike natural language with sequential tokens and decaying contextual relevance, table data exhibits rigid column-wise structures that induce distinct dependency patterns. 

We provide an information-theoretic framework to analyze long-context dependencies in table data. We show that tables preserve \textbf{periodic non-vanishing} structural dependencies, in contrast to the power-law decay observed in natural language. To our knowledge, this is the first mutual information-based analysis of tabular dependency structures. These properties make table data well suited for training long-context reasoning capability of LLMs.

\subsection{Background: Dependency Decay in Natural Language}

For natural language sequences, empirical studies~\cite{li1989mutual,lin2016critical} demonstrate that Mutual Information (MI) between tokens decays polynomially with distance ($d$):
\begin{equation}
I_{text}(d) \sim C \cdot d^{-\alpha}, \quad \text{with } \alpha \approx 0.5
\label{eq:powerlaw}
\end{equation}
This power-law decay, which we adopt as a modeling assumption for natural language throughout this work, implies $\lim_{d \rightarrow \infty} I_{text}(d) = 0$. A natural question arises: \textit{does table data exhibit the same decay pattern?}

\subsection{Setup: Table Data and Linearization}

A table $\mathcal{T}$ is an $n \times m$ structure with column headers $\mathcal{H} = \{H_1, \ldots, H_m\}$ and cells $\{T_{i,j}\}_{i \in [n], j \in [m]}$, where $[n] := \{1, \ldots, n\}$ and each cell $T_{i,j}$ is drawn from a column-specific distribution $P_j$. The row-major linearization $\phi: \mathcal{T} \rightarrow W_{1:L}$ maps a table to a token sequence $\phi(\mathcal{T})$:
\begin{equation*}
[H_1, \ldots, H_m, \underbrace{T_{1,1}, \ldots, T_{1,m}}_{\text{row 1}}, \underbrace{T_{2,1}, \ldots, T_{2,m}}_{\text{row 2}}, \ldots, T_{n,m}]
\end{equation*}
with total length $L = m(n+1)$, where $W_t$ denotes the $t$-th token. For position $t > m$ in the data region, let $\text{col}(t) \in [m]$ denote its column index.

For lag $d \in \{1, \ldots, L-m-1\}$, define the average MI over the data region:
\begin{align*}
\bar{I}_{table}(d) &= \frac{1}{|\mathcal{S}_d|} \sum_{t \in \mathcal{S}_d} I(W_t; W_{t+d}), \\
\mathcal{S}_d &= \{t : m < t \leq L - d\}
\end{align*}

Our analysis rests on the following assumptions (formal statements in Appendix~\ref{app:assumptions}):
\begin{itemize}
    \item[(A1)] \textit{Column Semantic Consistency}: All cells in column $j$ share the same distribution $P_j$.
    \item[(A2)] \textit{Column Distribution Distinctiveness}: Different columns have distinguishable distributions, i.e., $D_{KL}(P_j \| P_k) > 0$ for $j \neq k$, where $D_{KL}$ denotes the Kullback-Leibler divergence.
\end{itemize}
We do \textbf{not} assume that cells within the same column are conditionally independent; our results hold regardless of intra-column dependencies (see Remark~\ref{rmk:intra_col} in the Appendix).

\subsection{Periodic Non-Vanishing Dependencies}

We first introduce a key factor. Let $J \sim \text{Uniform}([m])$ be a randomly chosen column index.

\begin{definition}[Same-Column Mutual Information]
\label{def:same_col_mi}
The same-column MI is defined as:
\begin{equation}
I^{same} := I(T_{i,J}; T_{k,J})
\end{equation}
\end{definition}
As shown in Lemma~\ref{lem:same_col}, under Assumptions (A1)--(A2): (i) $I^{same} > 0$, and (ii) $I(T_{i,J}; T_{k,J}) = I^{same}$ for any $i \neq k$, i.e., same-column MI is independent of row distance.

The magnitude of $I^{same}$ depends on how distinguishable the column distributions are. As characterized in Proposition~\ref{prop:isame_characterization}, $I^{same}$ is determined by the cross-column variance $\sum_a \text{Var}_j[P_j(a)]$, where $\text{Var}_j[\cdot]$ denotes variance across columns. When column distributions are highly distinct, this variance is large, yielding larger $I^{same}$.

\begin{theorem}[Periodic Non-Vanishing Dependency]
\label{thm:main}
Under Assumptions (A1)--(A2), for any table with $n$ rows and $m$ columns:
\begin{equation}
\bar{I}_{table}(km) = I^{same} > 0, \quad \forall k \in \{1, 2, \ldots, n-1\}
\end{equation}
That is, $\bar{I}_{table}(d)$ attains periodic peaks of constant height $I^{same}$ at every multiple of the column count $m$.
\end{theorem}

Note that non-vanishing property holds \textit{specifically at periodic lags} $d = km$; at others, average MI may be smaller.

\begin{corollary}[Asymptotic Non-Decay]
\label{cor:liminf}
For a sequence of tables with $n \to \infty$ rows and fixed $m$ columns, under Assumptions (A1)--(A2):
\begin{equation}
\liminf_{d \rightarrow \infty} \bar{I}_{table}(d) \geq I^{same} > 0
\end{equation}
This contrasts starkly with natural language, where $\lim_{d \rightarrow \infty} I_{text}(d) = 0$ based on Eq.~\eqref{eq:powerlaw}.
\end{corollary}

\begin{corollary}[Asymptotic Dominance over Natural Language]
\label{cor:ratio}
Under the power-law assumption Eq.~\eqref{eq:powerlaw} for natural language and Assumptions (A1)--(A2) for tables:
\begin{equation}
\lim_{k \rightarrow \infty} \frac{\bar{I}_{table}(km)}{I_{text}(km)} = +\infty
\end{equation}
\end{corollary}

\subsection{Effective Dependency Distance}

\begin{definition}[Effective Dependency Distance~\cite{liu2008dependency}]
\label{def:eff_dist}
Given threshold $\tau > 0$: $D_{eff}(\tau) = \sup\{d : I(d) \geq \tau\}$.
\end{definition}

\begin{theorem}[Effective Distance Comparison]
\label{thm:eff_dist}
Under the power-law assumption Eq.~\eqref{eq:powerlaw} for natural language and Assumptions (A1)--(A2) for tables, for any $\tau \in (0, I^{same})$:
\begin{equation}
D_{eff}^{table}(\tau) = +\infty, \quad \text{while} \quad D_{eff}^{text}(\tau) < +\infty
\end{equation}
\end{theorem}

This result shows that for any threshold $\tau < I^{same}$, tabular dependencies exceed $\tau$ at infinitely many lags (specifically, at all $d = km$), whereas natural language dependencies eventually fall below $\tau$ permanently.

These results indicate that structured table data with periodic non-vanishing structures exhibits strong potential for long-context reasoning.