원문 초록
We initiate a resource-aware theory of \textit{language generation in the limit} under the minimal constraint of space efficiency. In our framework, a learner observes an adversarial positive stream from a target language $K$ and must eventually output a hallucination-free hypothesis language $L \subseteq K$ while omitting at most $Δ$ strings of $K$. We focus on $\mathcal{C}_{s,k}$, the collection of languages recognized by DFAs with at most $s$ states over an alphabet of size $k$, as the natural hypothesis class for memory-bounded learners. In the exponential-space regime, we prove that a learner can exactly identify the target $K$. Under a stricter memory budget, we characterize the strongest possible generation guarantees. In particular, we present a streaming algorithm using $\mathrm{poly}(s,k)$ space that converges to a hypothesis with generation gap $Δ= O(k^{2s-2})$. Moreover, the learned hypothesis captures every string in $K$ of length at least $2s-1$. We complement this result with a near-matching lower bound through a reduction from a standard communication complexity problem. Specifically, achieving generation gap $Δ\le k^{(1-\varepsilon)s}$ requires $k^{Ω(\varepsilon s)}$ memory. Together, these results reveal a sharp transition between polynomial-space generation and exponential-space exact identification.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.25777v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
PACE-dLLM: 확산 언어 모델을 위한 신뢰도 절벽 추정 기반 탄력적 블록 디코딩
PACE-dLLM: Elastic Block Decoding via Confidence Cliff Estimation for Diffusion Language Models
트랜스포머 언어 모델의 순차 연산 증류
Distilling Sequential Computation in Transformer Language Models
트랜스포머 언어 모델은 자기회귀적으로 시퀀스를 토큰 단위로 처리하므로, 컨텍스트가 길어질수록 비용이 점점 커진다. 그러나 인접한 많은 토큰 구간은 예측 가능성이 높거나 안정적인 단위로 자주 등장하여, 이들의 표현은 압축 가능할 수 있음을 시사한다. 우리는 입력 토큰 구간을 경량 merge 모듈이 즉석에서 계산하는 축약 표현으로 대체함으로써 순차 연산을 증류하는 방법을 제안한다. 이 모듈은 정적 토큰 임베딩 시퀀스로부터 여러 토큰의 기능적 역할을 포착하는 단일 대리 임베딩을 생성하여, 사전학습된 모델이 아키텍처 변경이나 재학습 없이 압축된 입력으로 동작할 수 있게 한다. 이 접근법을 추론 시 프롬프트와 중간 디코딩 단계 모두를 압축하는 데 적용하며, 롤백 메커니즘으로 저장된 다중 토큰 KV 캐시 항목을 단일 단계 대리 표현으로 대체한다. 다양한 모델에 걸친 실험에서 merge 모듈을 사용하면 언어 모델링 평가와 질의응답, 요약, 상식 추론, 장문 수학적 추론 등 다운스트림 과제에서 정확도 저하를 최소화하면서 유효 시퀀스 길이를 최대 40%까지 줄일 수 있음을 보였다. merge 모듈에 대한 추가적인 경량 적응은 일부 설정에서 정확도-압축 트레이드오프를 더욱 개선한다. 이 결과는 트랜스포머에서의 순차적 토큰 연산이 모델 갱신 없이 원래 동작을 근사하는 응축된 대리 표현을 통해 효과적으로 근사될 수 있음을 보여준다.
PRISM-VLM: 소형 비전-언어 모델을 위한 다축 변별 벤치마크
PRISM-VLM: A Multi-Axis Discriminative Benchmark for Compact Vision-Language Models
소형 비전-언어 모델(VLM)은 이제 멀티모달 애플리케이션의 점점 더 큰 비중을 뒷받침하고 있다. 그러나 이들을 비교하는 데 사용되는 벤치마크는 프런티어 모델 중심의 설계를 그대로 따르고 있다. 즉, 각 모델을 단일 정확도 수치로 환원함으로써, 포화된 평가 세트에서는 모델 간 격차가 좁아지고 더 어려운 평가 세트에서는 모델들이 낮은 점수대에 몰리게 된다. 본 논문에서는 반복적으로 나타나는 실패 양상(과제 품질, 행동적 견고성, 능력 병목)을 아우르는 일곱 개의 축에 따라 모든 항목을 채점하고 이를 하나의 PScore로 결합하는 다축 변별 벤치마크 PRISM-VLM을 소개한다. 항목은 15개의 공개 벤치마크에서 재활용하였다. 지난 2년간 발표된 소형 VLM들을 대상으로 한 실험에서, PScore는 항목 단위 쌍체 부트스트랩(item-level paired bootstrap) 하에서 기존의 단일 축 벤치마크보다 모델 쌍을 더 신뢰성 있게 구분하며, 이러한 벤치마크가 평균화 과정에서 가려 버리는 행동적 차이를 드러낸다. PScore가 통계적으로 구분되지 않는 모델들조차 축별 프로파일에서는 크게 갈리며, 특히 단일 프롬프트 정확도와 거의 직교하는 아첨(sycophancy) 축에서 두드러진다. 전체 파이프라인, 프롬프트, 항목별 주석을 공개할 예정이다.
병렬 Drafter가 병렬 추측 디코딩을 만날 때
When Parallel Drafter Meets Parallel Speculative Decoding
DSpark 스타일의 병렬 drafter는 추측 디코딩(speculative decoding)을 매우 효과적으로 만들었지만, draft 단계는 여전히 매 라운드 임계 경로(critical path)에서 직렬로 실행된다. 병렬 추측 디코딩(PSD)은 drafting과 검증(verification)을 겹치게 하지만, 기존 방법은 수용된 접두 문맥(prefix)과 보너스 토큰(bonus token)을 미리 추측해야 하며, 잘못된 추측은 전체 배치를 직렬 drafting으로 되돌린다. 우리는 효과적인 병렬 drafter를 재사용하면서도 매 라운드마다 백본–검증 겹침을 보장해 이러한 확률적 fallback을 완전히 없애는 PSD 프레임워크인 DPara를 제안한다. target이 검증하는 동안 DPara의 diffusion 백본은 보너스를 정하지 않은 채 모든 acceptance boundary에 대한 draft representation을 미리 계산하고, 경량 자기회귀(autoregressive) head가 드러난 검증 결과와 대응하는 사전 계산 representation을 결합해 다음 라운드의 draft 토큰을 거의 즉시 내보낸다—지배적인 백본 forward를 검증과 완전히 병렬화하고 무시할 수 있는 head 비용만 직렬로 남긴다. Qwen3-8B와 Qwen3-14B에 대해 수학·코딩·채팅 벤치마크 7개에서의 실험은 DPara가 자기회귀 디코딩 대비 평균 $3.21\times$ 및 $3.52\times$ 속도 향상을 달성하며, 가장 강한 직렬·병렬 추측 디코딩 baseline을 모두 능가함을 보여준다.
Jev는 방사선학 보고서를 판정할 수 있는가? 임상 사실성 평가를 위한 System One 모델
Can Jev Judge Radiology Reports? Evaluating a System One Model for Clinical Factuality
AI가 생성한 방사선학 보고서는 이상 소견을 누락하거나, 근거 없는 소견을 추가하거나, 그 존재 여부를 뒤집는 등의 문제가 있으면서도 의사가 작성한 보고서와 유사해 보일 수 있다. 이러한 사실적 차이를 측정하는 것은 보고서 생성기를 평가하는 데 필수적이다. 우리는 의사가 작성한 참조 보고서와의 일치를 판정하는 단순하고 저비용의 judge로서 System One 의사결정 모델 Jev를 연구한다. 우리의 평가기는 각 진술이 다른 보고서에 의해 뒷받침되는지 검사하고, 근거 없는 주장과 누락을 포착하기 위해 양방향으로 이러한 판정을 결합한다. 단일 질문 구성은 전문가 오류 수를 기준으로 RadEvalX에서 Kendall 상관 0.573, RadEvalExpert에서 0.398에 이르며, 동일한 분해 및 집계 조건에서 공개 자연어 추론(NLI) judge를 능가한다. 진술당 support 질문 하나는 판정 입력 토큰을 43–45% 적게 사용하면서도 일곱 개 질문과 유사한 전문가 일치를 유지한다. 문서화된 API 가격 기준으로, 로컬 분해를 제외하면 판정 비용은 보고서 쌍 100개당 3센트 미만이다. 별도의 통제 오류 테스트에서 Jev는 AUROC 0.977로 false negation을 탐지한다. 로컬 RadMatch는 두 전문가 데이터셋 모두에서 임상적으로 중요한 오류에 대해, 공유 RadEvalExpert 부분집합에서는 전체 오류에 대해 더 강한 일치를 달성한다. 소견 수 및 오류 범위 분석은 벤치마크 일치가 의료 오류 탐지뿐 아니라 보고서 크기와 오류 정의에도 반영됨을 보여 준다. 이러한 결과는 생성된 방사선학 보고서의 사실적 차이를 측정하는 실용적인 판정 구성요소로서 Jev를 뒷받침하며, 더 정교한 평가가 여전히 가치 있는 지점을 밝힌다.
효율적인 추론을 향하여: 확산 언어 모델을 위한 인과적 지름길 학습
Towards Efficient Reasoning: Learning Causal Shortcuts for Diffusion Language Models
확산 언어 모델(Diffusion Language Models, DLM)은 뛰어난 추론 능력으로 상당한 주목을 받아왔습니다. 그러나 양방향 어텐션(bidirectional attention) 메커니즘 하에서 DLM은 자기회귀 모델(autoregressive models, ARM)에 비해 기하급수적으로 큰 탐험(exploration) 공간에서 작동하므로, 무작위 마스킹 환경에서 추론을 유도하는 토큰에 집중하기 어렵습니다. 본 논문에서는 전체 시퀀스를 포괄하며 올바른 추론 궤적으로 명시적인 가이드를 제공하는 토큰 체인을 인과적 지름길(causal shortcut)로 정의합니다. DLM의 추론 정확도와 수렴(convergence) 속도에 인과적 지름길이 미치는 영향을 분석한 결과, 정답 수렴 효율성과 생성 정확도가 크게 향상됨을 확인했습니다. 이에 영감을 받아, 본 연구에서는 DLM을 위한 인과적 지름길 학습(Causal Shortcut Learning, CSL) 프레임워크를 제안합니다. 구체적으로, 데이터에서 인과적 지름길을 추출하는 단계별 토큰 추출 절차를 도입하고, 학습(training) 중 이러한 토큰들에 병렬 우선순위 마스킹을 적용하여 인과적 지름길을 통해 정답으로의 효율적이고 정확한 수렴을 가능하게 합니다. 여러 추론 벤치마크와 두 가지 기본 모델에 걸친 광범위한 실험을 통해 CSL이 기존 SFT 변형 베이스라인들을 일관되게 능가하며, SFT 전용 모델 대비 평균 $1.92\%$, MATH-500에서는 최대 $4.20\%$의 향상을 달성함을 입증합니다. 코드는 \href{https://github.com/ZJUDianJin/Causal-Shortcuts-Learning}{https://github.com/ZJUDianJin/Causal-Shortcuts-Learning 에서 확인할 수 있습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.